Содержание
- 2. Первой работой теории графов как математи-ческой дисциплины считают статью Эйлера (1736 г.), в которой рассматривалась задача
- 3. В 1905 году был построен Императорский мост, кото-рый был впоследствии разрушен в ходе бомбарди-ровки во время
- 4. Элементы теории графов Под графом G(X,U) понимают совокупность непустого множества X и подмножества U, представляющего собой
- 5. Вершина xi инцидента ребру (дуге) uj если она является началом или концом ребра (дуги). Аналогично утверждение,
- 6. Вершина степени 1 называется висячей. Вершина степени 0 называется изолированной. 7 Неограф Орграф ρ(x1) = ρ(x3)
- 7. Граф называется простым, если любые две его вершины соединены не более чем одним ребром, и каждое
- 8. Граф, любая пара вершин которого связана, называют связным графом. В связном графе, перемещаясь по ребрам из
- 9. Циклом называют последовательность ребер u1=(x1, xi), ..., uk=(xj, x1), при которой в результате обхода вершин графа
- 10. Большое значение в практических задачах имеют эйлеровы и гамильтоновы циклы. Эйлеров цикл – это цикл, в
- 11. Необходимым и достаточным условием наличия в конечном связном графе эйлерова цикла является четность степеней всех его
- 12. Граф с гамильтоновым циклом изображен на рисунке. Гамильтонов цикл обозначен штрих-пунктирной линией.
- 13. Для гамильтонова цикла общий критерий сущест-вования не известен. Существуют лишь частные критерии наличия в графе гамильтонова
- 14. При размещении графа в виде геометрической фигуры существует большая свобода в размещении вершин графа в пространстве
- 15. Если в графе G(X, U) опущены некоторые ребра, а число вершин осталось прежним, то полученный граф
- 16. Связный неориентированный граф, не содержа-щий циклов, называют деревом и обозначается T(X, W). Число ребер дерева |W|
- 18. Среди различных деревьев выделяют два важных частных случая: последовательное дерево (а), представляющее собой простую цепь, и
- 19. Характеристические числа графов Рассмотрим некоторые характеристические числа графа, не зависящие от изоморфных преобразований. Такие числа называют
- 20. Для несвязного графа с p компонентами связности, цикломатическое число υ (G) = r – n +
- 21. Задача раскраски вершин графа формулируется следующим образом. Необходимо раскрасить вершины графа таким образом, чтобы смежные вершины
- 22. Такие графы называют бихроматическими, двудольными графами или графами Кенига и обозначают G(X1, Х2, U). В отличие
- 23. Т.е., плоскостность это свойство его геометрической реализации на плоскости, а планарность – свойство графа быть реализованным
- 24. Минимальное число ребер, которое нужно удалить из графа, чтобы он стал планарным, называется числом планарности и
- 25. Число внутренней устойчивости. Множество вершин Хs графа G(X,U) называется внутренне устойчивым (независимым), если никакие две вершины
- 26. Для графа G(X,U), изображенного на рисунке, множества вершин {x3, x6}, {x4, x6}, {x1, x3, x7}, {x1,
- 27. Число внешней устойчивости. Множество вершин Хs графа G (X,U) называется внешне устойчивым (доминирующим), если каждая вершина
- 28. Для графа G (X,U), изображенного на рисунке, множества вершин {x1, x3, x7}, {x2, x4, x5, x8}
- 29. Плотность графа. Максимальный полный подграф графа G (X,U) называется кликой графа G; другими словами, клика графа
- 30. Для графа G(X,U), изображенного на рис. клику образуют вершины (2, 3, 6, 7). Плотность этого графа
- 31. На рисунке а изображен граф Петерсена. В результате стягивания графа (замена вершин x1 и x6 на
- 32. Способы задания графа 1. Явное задание графа. 2. Геометрический. 3. Матрица смежности. 4. Матрица инцидентности. 2.
- 34. Основные задачи теории графов Выбор проекта. Имеется n проектов, которые должны быть выполнены, и для выполнения
- 35. Максимальное независимое множество графа G представляет максимальное множество проектов, которое можно выполнить одновременно за один и
- 36. (а) Размещение телевизионных или радиопередающих станций на некоторой территории; (б) Размещение военных баз, контролирующих данную территорию;
- 37. Требуется найти наименьшее число военных баз и места их размещения, обеспечивающих контроль всей территории. Задача о
- 38. Каждая кандидатура владеет некоторым подмно-жеством из указанного множества языков. Необхо-димо выбрать каких переводчиков нанять, чтобы затраты
- 39. 3. Раскраски Граф G называется r-хроматическим, если его вершины могут быть раскрашены с использова-нием r цветов
- 40. Гипотеза четырех красок. Задача заключается в том, чтобы раскрасить географи-ческую карту так, чтобы пограничные страны были
- 41. В 1890 году английский математик П. Хивуд доказал, что любую карту на плоскости можно раскрасить в
- 42. Чтобы развеять все оставшиеся сомнения относи-тельно доказательства Аппеля – Хакена, в 1997 году Робертсон, Сандерс, Сеймур
- 43. Задача размещения Необходимо разместить n каких-то предметов по ящикам. Строим граф G в котором каждой вершине
- 44. 4. Размещение центров В практической деятельности постоянно возникают задачи «наилучшего» размещения оборудования в сетях или графах.
- 45. В других задачах необходимо минимизировать сумму всех расстояний от вершин графа до центра обслуживания (размещение склада
- 46. 5. Деревья Одно из наиболее важных понятий теории графов. Остовное дерево — ациклический связный подграф данного
- 47. Необходимо проложить линии коммуникаций (дороги, линии связи, электропередач и т.п.) между n заданными "точечными" объектами, при
- 48. Задача Штейнера В задаче определения SST ребрами покрывались все вершины множества Х. В практике встречаются задачи,
- 49. У минимального остовного дерева суммарная длина ребер - 10,123, а у дерева Штейнера суммарная длина ребер
- 50. Для отыскания точки Р, ближайшей (в смысле суммарного расстояния) к заданным точкам А, B, C, сначала
- 51. 6. Кратчайшие пути Пусть дан граф G(X, Γ), ребрам которого приписаны веса (стоимости), заданные матрицей C=||cij||m×m.
- 52. 2. Самый длинный (критический) путь. Задача сетевого планирования, заключающаяся в нахождении самого длинного по временной протяженности
- 53. 7. Эйлеровы циклы и задача китайского почтальона Ребрам графа G приписаны положительные веса. Требу-ется найти цикл,
- 54. д) наилучший метод работы автоматических вентиляционных устройств. е) уборка помещений и коридоров в больших учреждениях. ж)
- 55. Возникает вопрос о том, может ли быть найдена цикли-ческая последовательность производства продуктов рi (i = 1,
- 56. Задача коммивояжера В задаче коммивояжера рассматривается n городов и матрица попарных расстояний между ними. Требуется найти
- 57. 9. Потоки в сетях. 10. Паросочетания, транспортная задача Одна из наиболее интересных и важных задач в
- 58. Теорема Холла [1935] о свадьбах. Пусть G = (V1, V2, E) — двудольный граф. Тогда паросочетание,
- 59. Также задано сij – затраты на перевозку единицы продукта от i – го пункта производства до
- 60. Законы Мэрфи для программистов. Теория ошибок Если отладка - процесс удаления ошибок, то программирование должно быть
- 61. 5. Указание начинающему программисту. Если вы с первого раза сумели написать программу, в которой транслятор не
- 62. 13. Ошибки допускают многократное вложение друг в друга. Две одинаковые вложенные ошибки называются четной ошибкой и
- 63. 21. Программа-транслятор, предназначенная для перевода программ с языка высокого уровня на машинный язык, при переводе порождает
- 66. Скачать презентацию