На головну

перерахування графів

  1. Ізоморфізм і гомеоморфизм графів.
  2. Використання графів при вирішенні задач
  3. Позначення теорії графів
  4. Основи мережевого моделювання та теорія графів. Основні методи розрахунку мережевих моделей. Узагальнені детерміновані мережеві моделі.
  5. Оцінка числа неізоморфних графів з q ребрами
  6. Подання графів в комп'ютері

Визначення.Нехай дано графи G і H на одних і тих же занумерованих вершинах  . Тоді графи називаються рівними (G = H), якщо у них збігається безліч вершин і безліч ребер.

приклад:

 , Так як в графі G немає ребра  , А в графі H це ребро є, тобто безлічі ребер не збігаються.

Поставимо 3 завдання і вирішимо їх за допомогою апарату комбінаторики. Зауважимо, що кожному графу відповідає матриця суміжності і навпаки.

Завдання 1. Скільки всього графів без петель і кратних ребер з p вершинами?

Рішення: Побудуємо матрицю суміжності, вона виглядає наступним чином:

Для вирішення завдання треба підрахувати число всіляких варіантів в заштрихованої області. Заштрихованная область має  позицій. Тоді графів буде  , Так як в кожній позиції може бути 0 або 1.

Завдання 2. скільки  -графов без петель і кратних ребер?

Рішення: На головній діагоналі матриці суміжності стоять одні 0, так як граф без петель. Матриця складається з 0 і 1, так як граф без кратних ребер. Матриця симетрична, так як граф неорієнтований. число  -графов - це число способів розстановки в заштрихованої області q одиниць, тобто .

Завдання 3. скільки  -графов без петель, але з кратними ребрами?

Рішення: Матриця симетрична, на головній діагоналі нулі, складається з чисел множини {0,1, ..., q} (тобто кожна позиція матриці зайнята числом з безлічі {0,1, ..., q}).

число  -графов без петель, але з кратними ребрами, - це число способів розстановки з повтореннями q чисел на місцях  , Тобто  (Q - поєднання з повтореннями з  ).

Визначення.Графи G і H називаються ізоморфними , Якщо існує взаємно однозначна відповідність між їх вершинами і ребрами таке, що відповідні ребра з'єднують відповідні вершини, в іншому випадку графи G і H називаються неізоморфних .

Зауваження. По іншому  (Ізоморфні), якщо існує взаємно однозначна відповідність між множинами їх вершин, яке зберігає суміжність, тобто якщо ,  , то  , де , .

приклад:

 а)


 , І це відповідність зберігає суміжність.

б)

 , Так як суміжності не зберігається.

в)

5.6. Оцінка числа неізоморфних графів
с p вершинами

нехай  (P) - безліч графів з p вершин,  (P) - безліч всіх неізоморфних графів з  (P) (різних з точністю до ізоморфізму). Очевидно, що |  (P) | ? |  (P) |, де  (P) і  (P) - кінцеві.

Беремо будь-який граф G  (P), тоді влаштовуючи перенумерованіе p вершин, можна отримати p! інших вершин. Значить, з кожного графа G  (P) можна отримати не більше p! графів. А оскільки кожен граф з  (P) виходить переробкою, то

(1)

Співвідношення (1) дає оцінку числа неізоморфних графів з
р вершинами.

 



Попередня   41   42   43   44   45   46   47   48   49   50   51   52   53   54   55   56   Наступна

Завдання для самостійної роботи | Схеми з функціональних елементів | Визначення схем з функціональних елементів | Найпростіші методи синтезу | метод Шеннона | Спеціальне подання функцій | метод синтезу | Завдання для самостійної роботи | Елементи теорії графів | Способи завдання графа |

© um.co.ua - учбові матеріали та реферати