• Гідрологія і Гідрометрія
• Господарське право
• Економіка будівництва
• Економіка природокористування
• Економічна теорія
• Земельне право
• Історія України
• Кримінально виконавче право
• Медична радіологія
• Методи аналізу
• Міжнародне приватне право
• Міжнародний маркетинг
• Основи екології
• Предмет Політологія
• Соціальне страхування
• Технічні засоби організації дорожнього руху
• Товарознавство продовольчих товарів

Основні визначення

Лекція № 12. НЕОРІЄНТОВАНІ ГРАФИ

Граф – це сукупність двох множин|безлічі|: вершин і ребер , між якими визначено відношення|ставлення| інцидентності.

Кожне ребро e з|із| E інцидентно рівно двом вершинам і , які воно сполучає|поєднує,з'єднує|. При цьому вершина і ребро e називаються інцидентними один одному, а вершини і називаються суміжними.

Прийнято позначення n для числа вершин графа (потужність множини|безлічі| ): і m для числа його ребер: . Говорять, що граф G є (n, m) граф, де n – порядок|лад| графа, m – розмір графа.

Якщо всі ребра графа неорієнтовані, тобто пари вершин, які визначають елементи множини E, неврегульовані, то такий граф називається неорієнтованим графом, або неографом|. На мал. 12.1 показаний приклад|зразок| неографа|. Цей граф має п'ять вершин і шість ребер.

Мал. 12.1

Маршрут – послідовність ребер, в якій кожні два сусідні ребра мають загальну|спільну| вершину. Граф зв'язний, якщо будь-які дві вершини сполучені|з'єднані| хоч би одним маршрутом. Число ребер маршруту визначає його довжину.

Ребра, інцидентні одній парі вершин, називаються паралельними або кратними. Граф з|із| кратними ребрами називається мультиграфом.

Ребро називається петлею (кінцеві вершини співпадають|збігаються|). Граф, що містить|утримує| петлі і кратні ребра, називається псевдографом. На мал. 12.2 показаний псевдограф.

Мал. 12.2

Ступінь|міра| deg(v) вершини – це число ребер, інцидентних v. У неографі| сума ступенів|мір| всіх вершин рівна подвоєному числу ребер (лема про рукостискання):

. (12.1)

Петля дає внесок|вклад|, рівний 2, в ступінь|міру| вершини.

Статечна|поважна| послідовність – послідовність ступенів|мір| всіх вершин графа, записана в певному порядку|ладі| (за збільшенням або убуванню).

Приклад|зразок| 12.1. Статечна|поважна| послідовність неографа|, зображеного|змальованого| на мал. 12.1, записана за збільшенням, виглядає так:

=1, =2, =3, =3, =3.

Сума ступенів|мір| всіх вершин графа рівна:

.

Цей результат не суперечить|перечить| лемі про рукостискання, оскільки граф має шість ребер (m = 6).

Матриця суміжності графа – квадратна матриця A порядку|ладу| n, де елемент рівний числу ребер, що сполучають|поєднують,з'єднують| вершини i і j.

Приклад|зразок| 12.2. Граф, показаний на мал. 12.1, має наступну|таку| матрицю суміжності

.

Матриця інцидентності I – ще один спосіб опису графа. Число рядків цієї матриці рівне числу вершин, число стовпців – числу ребер; =1, якщо вершина v інцидентна ребру e; інакше =0. У кожному стовпці матриці інцидентності простого графа (без петель і без кратних ребер) міститься|утримується| по дві одиниці. Число одиниць в рядку рівне ступеню|мірі| відповідної вершини.

Приклад|зразок| 12.3. Граф, показаний на мал. 12.1, має наступну|таку| матрицю інцидентності

.

Граф називається підграфом графа , якщо і . Якщо , то підграф називається остовним|.

Компоненту зв'язності графа – максимальний по включенню|приєднанню| вершин і ребер зв'язкової підграф.

Ранг графа, де k – число компонент зв'язності.

Дерево – зв'язковий граф, що містить|утримує| n – 1 ребро.

Приклад|зразок| 12.4. На мал. 12.3 показане дерево, яке одночасно є|з'являється,являється| остовним| підграфом графа, показаного на мал. 12.1.

Мал. 12.3

Читайте також:

1. I визначення впливу окремих факторів
2. II. Визначення мети запровадження конкретної ВЕЗ з ураху­ванням її виду.
3. II. Мотивація навчальної діяльності. Визначення теми і мети уроку
4. II. Основні закономірності ходу і розгалуження судин великого і малого кіл кровообігу
5. Ocнoвнi визначення здоров'я
6. Адвокатура в Україні: основні завдання і функції
7. Алгебраїчний спосіб визначення точки беззбитковості
8. Амортизація основних засобів, основні методи амортизації
9. Аналіз службового призначення деталей та конструктивних елементів обладнання харчових виробництві, визначення технічних вимог і норм точності при їх виготовленні
10. Аналіз стратегічних альтернатив та визначення оптимальної стратегії формування фінансових ресурсів
11. Аналіз ступеня вільності механізму. Наведемо визначення механізму, враховуючи нові поняття.
12. Артеріальний пульс, основні параметри

Переглядів: 702