Содержание
- 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. Основные задачи теории графов 1. Независимые и доминирующие множества. Независимое множество (внутренне устойчивое мно-жество) есть множество
- 35. Максимальное независимое множество графа G представляет максимальное множество проектов, которое можно выполнить одновременно за один и
- 36. Размещение «центров», покрывающих заданную область (а) Размещение телевизионных или радиопередающих станций на некоторой территории; (б) Размещение
- 37. Требуется найти наименьшее число военных баз и места их размещения, обеспечивающих контроль всей территории. 3. Задача
- 38. Каждая кандидатура владеет некоторым подмно-жеством из указанного множества языков. Необхо-димо выбрать каких переводчиков нанять, чтобы затраты
- 39. 3. Раскраски Граф G называется r-хроматическим, если его вершины могут быть раскрашены с использова-нием r цветов
- 40. Гипотеза четырех красок. Задача заключается в том, чтобы раскрасить географи-ческую карту так, чтобы пограничные страны были
- 41. В 1890 году английский математик П. Хивуд доказал, что любую карту на плоскости можно раскрасить в
- 42. Задача размещения Необходимо разместить n каких-то предметов по ящикам. Строим граф G в котором каждой вершине
- 43. 4. Размещение центров В практической деятельности постоянно возникают задачи «наилучшего» размещения оборудования в сетях или графах.
- 44. В других задачах необходимо минимизировать сумму всех расстояний от вершин графа до центра обслуживания (размещение склада
- 45. 5. Деревья Одно из наиболее важных понятий теории графов. Остовное дерево — ациклический связный подграф данного
- 46. Необходимо проложить линии коммуникаций (дороги, линии связи, электропередач и т.п.) между n заданными "точечными" объектами, при
- 47. Задача Штейнера В задаче определения SST ребрами покрывались все вершины множества Х. В практике встречаются задачи,
- 48. У минимального остовного дерева суммарная длина ребер - 10,123, а у дерева Штейнера суммарная длина ребер
- 49. Для отыскания точки Р, ближайшей (в смысле суммарного расстояния) к заданным точкам А, B, C, сначала
- 50. 6. Кратчайшие пути Пусть дан граф G(X, Γ), ребрам которого приписаны веса (стоимости), заданные матрицей C=||cij||m×m.
- 51. 2. Самый длинный (критический) путь. Задача сетевого планирования, заключающаяся в нахождении самого длинного по временной протяженности
- 52. 7. Эйлеровы циклы и задача китайского почтальона Ребрам графа G приписаны положительные веса. Требу-ется найти цикл,
- 53. д) наилучший метод работы автоматических вентиляционных устройств. е) уборка помещений и коридоров в больших учреждениях. ж)
- 54. Задача коммивояжера В задаче коммивояжера рассматривается n городов и матрица попарных расстояний между ними. Требуется найти
- 55. 9. Паросочетания, транспортная задача
- 56. Возникает вопрос о том, может ли быть найдена циклическая последовательность производства продуктов рi (i = 1,
- 57. Задача размещения по критерию СДС состоит в минимизации функционала F(P) на множестве перестановок Р. Данная задача
- 58. Различные модификации общего метода отличаются способом расчета нижних границ и способом разбиения поля решений. Для описания
- 59. Таким образом, простейшая нижняя граница может быть получена при рассмотрении верхних половин матриц R и D
- 60. Пример. Разместить элементы, заданные взвешенным графом G (рис. (а)) на множестве позиций Р (рис. (б)). Составим
- 61. Для этого упорядочим составляющие вектора r в невозрастающем порядке, а вектора d – в неубывающем. r
- 62. Получим v(P) = r×d = 2 + 1 + 0 = 3. Таким образом, нижняя граница
- 63. Назначаем элемент e1 в позицию р2. 3. Помещаем элемент e2 в позицию р1. Размещены два элемента:
- 64. 5. Помещаем элемент e2 в позицию р4. Размещены два элемента: e1 в позиции р2 и e2
- 65. Неразмещенный элемент {e4}, свободная позиция {р3}; r1 ={4} и d 2={1}, r1×d2 = 4; r2 ={0}
- 66. Назначаем элемент e3 в позицию р3. 8. Неразмещенный элемент {e4}, свободная позиция {р1}. Помещаем {e4}в позицию
- 67. Законы Мэрфи для программистов. Теория ошибок Если отладка - процесс удаления ошибок, то программирование должно быть
- 68. 5. Указание начинающему программисту. Если вы с первого раза сумели написать программу, в которой транслятор не
- 69. 13. Ошибки допускают многократное вложение друг в друга. Две одинаковые вложенные ошибки называются четной ошибкой и
- 70. 21. Программа-транслятор, предназначенная для перевода программ с языка высокого уровня на машинный язык, при переводе порождает
- 72. Скачать презентацию