ПРИЛОЖЕНИЕ А (справочное)Элементы теории графов Граф представляет собой совокупность двух множеств: множества вершин (углов) и множества ребер (дуг). Вершина, которая является крайней точкой ребра, называется инцидентной ребру (а ребро соответственно инцидентно вершине). Две вершины с одним инцидентным ребром или два ребра с общей инцидентной вершиной называются смежными. Петля - ребро графа, инцидентное единственной вершине. Маршрут (путь) - конечная последовательность вершин, каждые две соседние вершины в которой являются смежными. Маршрут простой, если все и ходящие в него вершины различны. Цикл - маршрут, первая и последняя вершины которого совпадают. Простой цикл - цикл, в котором единственными совпадающими вершинами якняются первая и последняя. Гамильтонов цикл - простой цикл, содержащий все вершины графа. Граф, не имеющий простых циклов с более чем двумя различными вершинами, называют ациклическим. Граф является связным, если любые две сш вершины можно соединить маршрутом. Связный ациклический граф называется деревом. Например, граф на рисунке 10 состоит из вершин {А, В, С, D, Е, F) и ребер {а, b, с, d, е, f}. Вершине А, например, инцидентны ребра а, b и с; ребру c инцидентны вершины А и С; вершины А и В являются смежными (так как обе инцидентны ребру b); ребра с и d также смежные (так как оба инцидентны вершине С). Ребро а представляет собой петлю, так как инцидентно только вершине А. Маршруты АВС и АВСD являются простыми, а маршруты АВСВ и ABCA - нет, так как в первом из них вершина В повторяется дважды, а во втором вершина А. Но маршрут АВСА представляет собой простой цикл, так как первой и последней вершиной в нем является А, и никакие другие вершины в нем не повторяются. Маршрут АВСВА - также цикл, но он не является простым циклом (дважды повторяется вершина В). Так как в графе присутствует маршрут АВСА, граф не является ациклическим. Граф не является и связным, так как нельзя соединить маршрутом, например, вершины А и Е. Гамильтонов цикл в этом графе построить нельзя.
Рисунок 10 – Пример графа
Если рассматривать в качестве отдельного графа, например, граф состоящий из вершин {B, C, D,} и ребер {d, e}, то такой граф будет связанным и ациклическим, т.е. его можно назвать деревом. В графе, состоящем из вершин {A, B, C} и ребер {a, b, c, d}, маршрут АВСА будет представлять собой гамильтонов цикл, т.к. он простой и содержит все три вершины этого графа.
СОДЕРЖАНИЕ Введение.......................................................................................... 3 1 Цель работы.................................................................................. 4 2 Приборы и материалы................................................................. 4 3 Описание работы......................................................................... 4
3.1 Метод ветвей и границ. Общая схема..................................4 3.2Применение метода ветвей и границ к решению задач линейного целочисленного программирования 5 3.3 Пример решения задачи целочисленного линейного программирования методом ветвей и границ. 7 3.4Решение задачи целочисленного линейного программирования 3.5 Порядок выполнения работы.............................................. 14
4 Оформление результатов работы.............................................. 14 5 Контрольные вопросы............................................................... 15 Литература..................................................................................... 16 Приложение А. Элементы теории графов................................. 17
|
