Учебники

Теория графов – Примеры

В этой главе мы рассмотрим несколько стандартных примеров, чтобы продемонстрировать концепции, которые мы уже обсуждали в предыдущих главах.

Пример 1

Найдите количество связующих деревьев на следующем графике.

Пример Spanning Trees

Решение

Число связующих деревьев, полученных из приведенного выше графика, равно 3. Они следующие:

Полученные остовные деревья

Эти три являются связующими деревьями для данных графиков. Здесь графы I и II изоморфны друг другу. Ясно, что число неизоморфных остовных деревьев равно двум.

Пример 2

Сколько простых неизоморфных графов возможно с 3 вершинами?

Решение

Возможны 4 неизоморфных графа с 3 вершинами. Они показаны ниже.

Неизоморфный пример

Пример 3

Пусть ‘G’ – связный планарный граф с 20 вершинами и степень каждой вершины равна 3. Найдите количество областей в графе.

Решение

По теореме о сумме степеней

20 i = 1 градус (V i ) = 2 | E |

20 (3) = 2 | E |

| E | = 30

По формуле Эйлера,

| V | + | R | = | E | + 2

20+ | R | = 30 + 2

| R | = 12

Следовательно, количество регионов составляет 12.

Пример 4

Какое хроматическое число полного графа K n ?

Решение

Пример хроматического числа

В полном графе каждая вершина смежна с оставшимися (n – 1) вершинами. Следовательно, каждая вершина требует нового цвета. Следовательно, хроматическое число K n = n .

Пример 5

Какой совпадает номер для следующего графика?

Решение

Пример соответствия номера

Количество вершин = 9

Мы можем сопоставить только 8 вершин.

Соответствующий номер 4.

Соответствующий номер, пример 1

Пример 6

Какое количество строк покрывает число для следующего графика?

Решение

Пример номера покрытия линии

Количество вершин = | V | = n = 7

Номер покрытия линии = (α 1 ) ≥ ⌈ n / 2 ⌉ = 3

α 1 ≥ 3

Используя 3 ребра, мы можем покрыть все вершины.

Следовательно, номер покрытия строки равен 3.