Реферат Курсовая Конспект
Порядковая функция графа без контуров - раздел Математика, При каких условиях вершины графа можно раскрасить так, чтобы каждое ребро было инцидентно вершинам разного цвета Рассмотрим Граф Без Контуровg=(E,r) И Определим Подмножества N0, N1,…, N2:...
|
Рассмотрим граф без контуровG=(E,R) и определим подмножества N0, N1,…, N2:
N0=, Ǿ},
N1=-, },
N2=--, },
------------------------------------------------------------------------------------------------------------
N2=-},
Где 2 – такое наименьшее целое число, что rN2= Ǿ
Функция 0(x), определенное равенством , называемое порядковой функцией графа без контуров. Другими словами, предлагается разбить множество вершин графа без контуров на непересекающиеся подмножества, упорядоченные так, что если вершина принадлежит подмножеству с номером К, то следующая за ней вершина подмножества входит в подмножество с номером, большим К. Подмножество этого разбиения называются уровнями.
Порядковую функцию графа без контуров можно определить различными способами; в качестве начального множества можно взять произвольное множество вершин, содержащее N0 . Порядковая функция позволяет перенумеровывать вершины так, что вершины уровня Ni имеют номера меньшие, чем вершины уровня Ni+1 . Порядковая функция играет важную роль во многих комбинированных задачах.
Понятие порядковой функции для графов с контурами. Порядковая функция классов графа.
Алгоритм нарождения уровней графа без контуров (Дему Крон)
Выпишем букву матрицу графа G: матрицу смежности.
Образуем строкуЛ0, выписывая для каждой вершины количество предшествующих ей вершин. В качестве N0 берем т.о., такие вершины, которым не предшествуют никакие вершины (пусть 1 и 3). Затем берем строку Л1. На местах 1 и 3 ставим x, а на остальных количество вершин, предшествующих данной. Вершины, которым соответствует 0 в строке Л1, составляют уровень N1. Далее выписываем Л2,… и соответствующие уровни N2, N3,… до тех пор, пока это возможно. Если в графе есть контур, то обязательно появится строка Лi без нулей.
Пример:
A | B | C | D | E | F | G | H | I | J | K | L | M | N | ||
A | |||||||||||||||
B | |||||||||||||||
C | |||||||||||||||
D | |||||||||||||||
E | |||||||||||||||
F | |||||||||||||||
G | |||||||||||||||
H | |||||||||||||||
I | |||||||||||||||
J | |||||||||||||||
K | |||||||||||||||
L | |||||||||||||||
M | |||||||||||||||
N | |||||||||||||||
A | B | C | D | E | F | G | H | I | J | K | L | M | N | ||
Л0 | |||||||||||||||
Л1 | X | X | |||||||||||||
Л2 | X | X | X | X | X | ||||||||||
Л3 | X | X | X | X | X | X | X | X | |||||||
Л4 | X | X | X | X | X | X | X | X | X | ||||||
Л5 | X | X | X | X | X | X | X | X | X | X | X | X |
N0 N1 N2 N3 N4 N5
E B A F D C
H I G K
J N L
M
РАСПРЕДЕЛЕНИЕ ПО УРОВНЯМ
– Конец работы –
Эта тема принадлежит разделу:
При каких условиях вершины графа можно раскрасить так чтобы каждое ребро было инцидентно вершинам разного цвета Хроматическое... Обобщение Если Т произвольное дерево с п вершинами то Pt К К К Если... РG К К К К К п...
Если Вам нужно дополнительный материал на эту тему, или Вы не нашли то, что искали, рекомендуем воспользоваться поиском по нашей базе работ: Порядковая функция графа без контуров
Если этот материал оказался полезным ля Вас, Вы можете сохранить его на свою страничку в социальных сетях:
Твитнуть |
Новости и инфо для студентов