Фундаментальное множество циклов
Выбери формат для чтения
Статья: Фундаментальное множество циклов
Загружаем конспект в формате pdf
Это займет всего пару минут! А пока ты можешь прочитать работу в формате Word 👇
Фундаментальное множество циклов
T (n, n 1) остов графа G(n, m)
Элемент фундаментального множества циклов графа G(n, m)
относительно остова T (n, n 1) – это цикл, получающийся
при добавлении хорды в остов T (n, n 1) (всего таких циклов m n c)
1
2
1
2
1
2
1
с
2
1
5
3
5
3
4
4
8
6
с2
3
8
6
7
4
7
3
4
с3
6
(G) 12 8 1 5
5
5
с5
8
7
3
Матрица фундаментальных циклов
4
7
5
4
С
(1,3) (1,4) (3,6) (3,7) (5,8) (1,2) (2,4) (3,4) (4,5) (5,7) (6,7) (7,8)
с1 1 0 0
0 1
1 1 0
0 0 0
с2 0 1 0
0 1
1 0 0
0 0 0
с3 0
с4 0
1
1
1
1
1
1
1
1
1
с5 0
1
1
1
с4
7
1, e j ci
сij
0, e j ci
Разрез – множество ребер, удаление которых делает граф несвязным.
Простой разрез (минимальный) –
никакое подмножество ребер разрезом не является - коцикл
1
коцикл разбивает граф ровно на две компоненты связности
n 1 - коцикломатическое число графа
5
3
4
кодерево – часть графа, составленная из хорд
8
6
Построение фундаментального множества разрезов
Исключаем ветвь u T - получаем две компоненты связности
7
Хорды, соединяющие вершины разных компонент связности, и ребро u
образуют фундаментальный разрез относительно ребра u остова Т
1
2
n-1=8-1=7
2
1
3
4
3
4
3
4
8
7
3
4
6
1
2
5
3
6
1
4
7
6
3
5
3
5
6
8
6
8
5
7
7
7
7
1, e j ki
kij
0, e j ki
Матрица фундаментальных коциклов
1
2
1
5
3
4
4
3
6
K
3
4
4
3
5
5
k5
3
8
6
7
6
7
(1,3) (1,4) (3,6) (3,7) (5,8) (1,2) (2,4) (3,4) (4,5) (5,7) (6,7) (7,8)
k1 1 1 0
0 1
0 0 0
0 0 0
k2 1 1 0
0 0
1 0 0
0 0 0
k3 1
k4 0
k5 0
k6 0
k7 0
1
3
8
k4
2
k2
3
7
1
k1
4
6
2
k3
1
1
1
1
1
1
1
1
1
1
1
1
1
1
6
7
5
k6
k7
8
7
7
Раскраска вершин графов (для графов без петель)
f : V 1,2,...,k - вершинная k-раскраска графа G(V,E)
Правильная k-раскраска -для смежных вершин u и v f (u ) f (v)
Хроматическое число графа G – χ (G)
k – раскрашиваемый граф
минимальное число k, при котором G
является k-раскрашиваемым
Раскраска для графа G(n,m) существует в диапазоне
χ (G),n
Алгоритм последовательного раскрашивания
1) Выбираем вершину a0 и красим в первый цвет.
2) Вершины a0, a1, …, ai, раскрашены p цветами: 1,2,…p ( p i)
красим вершину ai+1 в минимальный цвет, не использованный при раскраске
смежных вершин.
(Для улучшения алгоритма выбираем вершину максимальной степени)
χ (G) 4
Задача расписания. Вершины – лекции.
Смежные вершины – не читаются одновременно
1
3
2
Оптимальное расписание - минимальная раскраска
{
5
4
6
…}
Задача о раскрашивании карты (1879 г. А.Кэли)
Гипотеза четырех красок: всякая карта 4-раскрашиваема.
Теорема. Каждый планарный граф 5-раскрашиваем
(1890 г. Р. Хивуд)
Теорема. Для любого графа G верно неравенство (G) 1 (G)
Доказательство. Метод математической индукции
(G) 1 (G) 0
(G) 1 (G)
2) n(G) n
1) n 1
n(G) n
(G) 1 (G)
v V (G)
(G \ {v}) 1 (G \ {v}) 1 (G)
deg v (G) хотя бы один цвет из 1 (G) свободен
Задача о раскрашивании ребер.
1
26
2
3
4
5
6
Монтаж аппаратуры:
L(G)
Вершины – платы;
Ребра - проводники
12
16
46
G
56
13
35
