Рубрики

Регулярный граф в теории графов

Условие: основы теории графов — набор 1 , набор 2

Обычный график:
Граф называется регулярным графом, если степень каждой вершины равна. Граф называется K регулярным, если степень каждой вершины графа равна K.

Пример:
Посмотрите на график ниже:

Степень каждой вершины этого графа равна 2. Итак, граф есть. Аналогично, ниже приведены графики и соответственно.

Свойства регулярных графов:

  1. Полный граф N вершин является регулярным.
    Доказательство :
    В полном графе из N вершин каждая вершина связана со всеми (N-1) оставшимися вершинами. Итак, степень каждой вершины равна (N-1). Таким образом, график является (N-1) регулярным.
  2. Для регулярного графа K, если K нечетно, то число вершин графа должно быть четным.
    Доказательство :
    Предположим, число вершин N нечетно.
    Из теоремы о рукопожатии мы знаем,
    Сумма степени всех вершин = 2 * Количество ребер графа ……. (1)
    RHS уравнения (1) является четным числом.

    Для регулярного графа K каждая вершина имеет степень K. Сумма степеней всех вершин = K * N, где K и N оба нечетные. Так что их произведение (сумма степеней всех вершин) должно быть нечетным. Это делает LHS уравнения (1) нечетным числом. Итак, LHS RHS Итак, наше первоначальное предположение, что N нечетно, было неверным. Итак, количество вершин (N) должно быть четным.

  3. Цикл (C n ) всегда 2 регулярный.
    Доказательство :
    В цикле (C n ) каждая вершина имеет двух соседей. Итак, они 2 регулярных.
  4. 2 Регулярные графики состоят из и.

  5. Число ребер K регулярного графа с N вершинами = (N * K) / 2.
    Доказательство :
    Пусть число ребер регулярного графа K с N вершинами равно E.
    Из теоремы о рукопожатии мы знаем,

    Сумма степени всех вершин = 2 * E
    N * K = 2 * E
    или E = (N * K) / 2

  6. K-мерный гиперкуб (Q k ) является K регулярным графом.
    Ниже 3-мерный Гиперкуб (Q 3 ), который является 3 Регулярным графом.

Рекомендуемые посты:

Регулярный граф в теории графов

0.00 (0%) 0 votes