Студопедия
Случайная страница | ТОМ-1 | ТОМ-2 | ТОМ-3
АрхитектураБиологияГеографияДругоеИностранные языки
ИнформатикаИсторияКультураЛитератураМатематика
МедицинаМеханикаОбразованиеОхрана трудаПедагогика
ПолитикаПравоПрограммированиеПсихологияРелигия
СоциологияСпортСтроительствоФизикаФилософия
ФинансыХимияЭкологияЭкономикаЭлектроника

Элементы теории графов

Читайте также:
  1. Quot;Основные права" в социалистической теории
  2. Аналитический способ задания графов
  3. Блок А. Элементы содержания, владение которыми на заданном уровне обязательно для получения удовлетворительной оценки
  4. Блок Б. Остальные элементы содержания.
  5. В-25. Новоевропейский рационализм эпохи Просвещения как основа обновления политико-правовой теории , секуляризации научного и культурного сознания.
  6. В-29. Идея разделения властей в п-п теории
  7. В-3. Взаимодействие формирующейся п-п теории с естественно-научными знаниями.

Граф представляет собой совокупность двух множеств: множества вершин (углов) и множества ребер (дуг).

Вершина, которая является крайней точкой ребра, называется инцидентной ребру (а ребро соответственно инцидентно вершине). Две вершины с одним инцидентным ребром или два ребра с общей инцидентной вершиной называются смежными. Петля - ребро графа, инцидентное единственной вершине.

Маршрут (путь) - конечная последовательность вершин, каждые две соседние вершины в которой являются смежными. Маршрут простой, если все входящие в него вершины различны.

Цикл - маршрут, первая и последняя вершины которого совпадают. Простой цикл - цикл, в котором единственными совпадающими вершинами являются первая и последняя.

Гамильтонов цикл - простой цикл, содержащий все вершины графа.

Граф, не имеющий простых циклов с более чем двумя различными вершинами, называют ациклическим. Граф является связным, если любые две его вершины можно соединить маршрутом. Связный ациклический граф называется деревом.

Например, граф на рис.17 состоит из вершин {A, B, C, D, E, F} и ребер {a, b, c, d, e, f}. Вершине А, например, инцидентны ребра а, b и с; ребру с инцидентны вершины А и С; вершины А и В являются смежными (так как обе инцидентны ребру b); ребра c и d также смежные (так как оба инцидентны вершине С). Ребро а представляет собой петлю, так как инцидентно только вершине А. Маршруты АВС и АВСD являются простыми, а маршруты АВСВ и АВСА – нет, так как в первом из них вершина В повторяется дважды, а во втором – вершина А. Но маршрут АВСА представляет собой простой цикл, так как первой и последней вершиной в нем является А, и никакие другие вершины в нем не повторяются. Маршрут АВСВА - также цикл, но он не является простым циклом (дважды повторяется вершина В). Так как в графе присутствует маршрут АВСА, граф не является ациклическим. Граф не является и связным, так как нельзя соединить маршрутом, например, вершины А и Е. Гамильтонов цикл в этом графе построить нельзя.

 

Если рассматривать в качестве отдельного графа, например, граф, состоящий из вершин {B, C, D} и ребер {d, e}, то такой граф будет связным и ациклическим, т.е. его можно назвать деревом. В графе, состоящем из вершин {A, B, C} и ребер {а, b, c, d}, маршрут АВСА будет представлять собой гамильтонов цикл, так как он простой и содержит все три вершины этого графа.



Дата добавления: 2015-08-27; просмотров: 46 | Нарушение авторских прав


<== предыдущая страница | следующая страница ==>
Постановка задачи целочисленного линейного программирования| Метод ветвей и границ. Общая схема

mybiblioteka.su - 2015-2024 год. (0.006 сек.)