Хроматическое число

Граф называется p – хроматическим, если его вершины можно раскрасить р различными цветами так, что никакие 2 смежные вершины не раскрашены одинаково.

Хроматическое число графа G: γ(G)=р.

Если γ(G)=2 – граф называется бихроматическим.

Необходимое и достаточное условие бихроматичности графа – отсутствие циклов нечетной длины.

б ихроматические не бихроматические

Дерево

Конечный связанный неориентированный граф, не имеющий циклов, называется деревом.

Несвязанный неориентированный граф, не имеющий циклов, называется лесом, а каждая его компонента связанности – деревом.

Теорема: любые две вершины дерева связаны одной и только одной цепью. Вершина со степенью равной единице называется концевой (висячей) вершиной, а инцидентное ей ребро, называется концевым.

Т еорема: каждое дерево имеет хотя бы 2 концевые вершины и 1 концевое ребро.

Иногда одну точку выделяют и называют корнем дерева.

Граф можно сделать ориентированным если идти от корня дерева к концевым вершинам (или наоборот). Такой граф называют ориентированным деревом. Путь от корня до концевой вершины называют ветвью. Вершину с максимальной степенью называют центром дерева.

Центр может быть не единственным (в этом случае говорят, что нет центра).

Примеры деревьев

1. Родословное дерево.

2. Структура предприятия.

3. Дерево целей, например,

S - национальная безопасность

S₁(готовн. к войне) S₂(демонстр. Силы)

и т.д.

4. Прогнозное дерево.

S причина

S₁ S₂ следствие

S₁₁ S₁₂ S₂₁ S₂₂ следствие следствия

5. Дерево задач.

S – освоение космоса

S – освоение Луны

S₁ – исследование S₂ – высадка человека

и т.д.

Изоморфизм графов

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

Точнее, графы изоморфны, если существует взаимнооднозначное соответствие между множеством вершин и ребер графа.

Изоморфные графы:

(А на самом деле из-за ошибки в рисунке один граф оказался не изоморфным. Найдите его!)

Неизоморфные графы: , хотя большинство характеристик совпадают.

У изоморфных графов, матрицы смежности и инцидентности, список ребер – совпадают. Перебрав все обозначения, рано или поздно получим одинаковые матрицы. А для неизоморфных графов матрицы не совпадут никогда.

Гиперграфы (сети, блок-схемы)

Множество вершин A={a₁,a₂,...a_n} и множество наборов, называемых полюсами, E={e₁,e₂,...e_m}, где ei = (a_i1...a_ij...), a_ij A, (то есть e – набор элементов из A), называется гиперграфом или сетью.

Обычно один из наборов е₀ называют внешним.

Пример.

A = (1,2,3,4,5,6)

e₀ = (1,5,6)

е₁ = (1,2,3,3,4)

е₂ = (2,4,5,6)

е₃ = (4,4,5)

Сеть, у которой e₀= , а для _i=1,2... е_i, – двухэлементное множество, является графом. При этом полюса e_i=(a_i1,a_i2) это ребра, связывающие две вершины a_i1 и a_i2, a_j – вершины графа.