Реферат Курсовая Конспект
Фундаментальные циклы - раздел Математика, Остовы графов Пусть G= Неорграф, Имеющий N Вершин, M Ребер И С Компонент Связности, T-Остов...
|
Пусть G= неорграф, имеющий n вершин, m ребер и с компонент связности, T-остов графа G. В §4.8 отмечалось, что T имеет v*(G)=n-c ребер u1, … , un-c, которые будем называть ветвями остова T. Оставшиеся m-n+с ребер v1, v2, … , vm-n+c , не входящие в T, будем называть хордами остова T. Согласно теореме 4.8.1, п. 5, если к лесу T добавить произвольную хорду vi , то в полученном графе найдется ровно один цикл, который обозначим через Ci. Цикл Ci состоит из хорды vi и некоторых ветвей остова T, которые принадлежат единственной простой цепи, соединяющей вершины хорды vi. Цикл Ci называется фундаментальным циклом графа G относительно хорды vi остова T. Множество всех фундаментальных циклов относительно хорд остова T называется фундаментальным множеством циклов графа G относительно остова T. Отметим, что мощность фундаментального множества циклов равна цикломатическому числу v(G)=m .
Обозначим через последовательность всех ребер графа G. Тогда фундаментальному циклу Ci соответствует вектор = , определенный по следующему правилу:
Теперь фундаментальное множество циклов можно задать с помощью матрицы фундаментальных циклов, строки которой являются векторами 1, 2, … , v(G):
C⇌ .
Так как каждый фундаментальный цикл Ci содержит ровно одну хорду, а именно , то матрица C имеет вид
C= .
Таким образом, C= , где единичная матрица порядка .
П р и м е р 4 .11.1. Найдем матрицу фундаментальных циклов графа G, изображенного на рис. 4.45.Так как =8 6+1=3, то для получения остова удаляем из графа три ребра. Сопоставим этим ребрам номера 1,2,3.
Ребрам, входящим в остов, поставим в соответствие номера 4,5,6,7,8. Легко видеть, что фундаментальный цикл , соответствующий хорде 1, состоит из ребер 1,4,6, цикл -из ребер 2,6,7, цикл C3-из ребер 3,6,7,8. Поэтому матрица фундаментальных циклов C имеет вид
C .
5 8
4 2
6 3
1 7
– Конец работы –
Эта тема принадлежит разделу:
тема quot Элементы теории графов Виды и способы задания графов quot... Даны населенные пункты расстояния между которыми известны Требуется найти маршрут проходящий через все пункты по...
Если Вам нужно дополнительный материал на эту тему, или Вы не нашли то, что искали, рекомендуем воспользоваться поиском по нашей базе работ: Фундаментальные циклы
Если этот материал оказался полезным ля Вас, Вы можете сохранить его на свою страничку в социальных сетях:
Твитнуть |
Новости и инфо для студентов