рефераты конспекты курсовые дипломные лекции шпоры

Раздел Математика
/
Порядковая функция графа без контуров

Реферат Курсовая Конспект

Выберите учебное заведение

Порядковая функция графа без контуров

Порядковая функция графа без контуров - раздел Математика, При каких условиях вершины графа можно раскрасить так, чтобы каждое ребро было инцидентно вершинам разного цвета Рассмотрим Граф Без Контуров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 без нулей.

Пример:

Л0

Л1

Л2

Л3

Л4

Л5

N0 N1 N2 N3 N4 N5

E B A F D C

H I G K

J N L

РАСПРЕДЕЛЕНИЕ ПО УРОВНЯМ

Развернуть

Открыть в широком формате

– Конец работы –

Эта тема принадлежит разделу:

При каких условиях вершины графа можно раскрасить так, чтобы каждое ребро было инцидентно вершинам разного цвета

При каких условиях вершины графа можно раскрасить так чтобы каждое ребро было инцидентно вершинам разного цвета Хроматическое... Обобщение Если Т произвольное дерево с п вершинами то Pt К К К Если... РG К К К К К п...

Если Вам нужно дополнительный материал на эту тему, или Вы не нашли то, что искали, рекомендуем воспользоваться поиском по нашей базе работ: Порядковая функция графа без контуров

Что будем делать с полученным материалом:

Если этот материал оказался полезным ля Вас, Вы можете сохранить его на свою страничку в социальных сетях:

Все темы данного раздела:

Хроматическое число
Пусть граф G петель, тогда G – K – раскрашиваемый, если каждой его вершине можно приписать один из К цветов, так чтобы никакие 2 смежные вершины не оказались одного цвета. Если G – К – рас

Раскраска
Граф G – ребро К- раскрашиваем, если его ребра можно раскрасить К красками таким образом, что никакие 2 смежных ребра не окажутся одного цвета. Если граф G ребро К – раскрашиваем, но не являются ре

Хроматические многочлены
ПустьG – простой граф, пусть РG(К) – число способов, которым можно окрасить вершины графа G, используя К красок и соблюдая условие: никакие 2 смежные вершины не должны иметь один и тот же цвет. Пус

Теоретико- множественное произведение: Понятие 2-выборки.
Пусть заданы 2 множеств (конечных или нет) Е, Е,...Е, причем Еi принадлежит Е, Еg принадлежит Е,…Еe принадлежит Е. Упорядоченная совокупность Рα=(Еi, Еg,…Ee)называется 2-выборной, и множество

Упорядочение 2-выборки
2-выборку, которая определена как Рα=(Ei, Eg,…Ee) и в которой порядок компонент фиксирован по определению, будем называть упорядоченной 2 –выборкой. Говорят, что 2 упорядоченный 2-выб

Неупорядоченные 2 – выборки.
Неупорядоченная 2-выборка не есть 2-выборка в смысле данного определения. Если в определении упорядоченной 2-выборки не учитывать порядок компонент, то приходим к неупорядоченной 2-выборке, которую

Производящая функция
Пусть ап, п принадлежит N – последовательность. Этой последовательности поставим в соответствии ряд по целым числам Z. F*(z)=a+az+az +…+az+… Предположим, что всегда су