В этой главе мы рассмотрим несколько стандартных примеров, чтобы продемонстрировать концепции, которые мы уже обсуждали в предыдущих главах.
Пример 1
Найдите количество связующих деревьев на следующем графике.
Решение
Число связующих деревьев, полученных из приведенного выше графика, равно 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.
Пример 6
Какое количество строк покрывает число для следующего графика?
Решение
Количество вершин = | V | = n = 7
Номер покрытия линии = (α 1 ) ≥ ⌈ n 2 ⌉ = 3
α 1 ≥ 3
Используя 3 ребра, мы можем покрыть все вершины.
Следовательно, номер покрытия строки равен 3.