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

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

Пример 1

Find the number of spanning trees in the following graph.

Решение

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

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

Пример 2

How many simple non-isomorphic graphs are possible with 3 vertices?

Решение

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

Пример 3

Let ‘G’ be a connected planar graph with 20 vertices and the degree of each vertex is 3. Find the number of regions in the graph.

Решение

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

20 Σ i = 1 град (Vi) = 2 | E |

20 (3) = 2 | E |

| E | = 30

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

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

20+ | R | = 30 + 2

| R | = 12

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

Пример 4

What is the chromatic number of complete graph Kn?

Решение

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

Пример 5

What is the matching number for the following graph?

Решение

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

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

Соответствующее число - 4.

Пример 6

What is the line covering number of for the following graph?

Решение

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

Число перекрытия линии = (α 1 ) ≥ [n / 2] = 3

α 1 ≥ 3

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

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