Графи та їх різновиди презентация

різноманітними видами інформації, організувати абстрактне їх представлення.

Графом називається сукупність точок (вершин) і ліній (ребер), що їх з'єднують.

вершинам, а вершини, які з'єднані таким ребром, називають суміжним.

2)Якщо кінці ребра належать одній вершині, то таке ребро називається петлею.

ізольованими.
Вершина А – приклад ізольованої вершини.

А

ГРАФ

ЛІС

ОРІЄНТОВАНИЙ ГРАФ

НЕОГРАФ

ОРГРАФ

ЗВАЖЕНИЙ ГРАФ

ЗМІШАНИЙ ГРАФ

ГРАФ,ЯК КОНФІГУРАЦІЯ

ЕЙЛЕРІВ ГРАФ

ЗВ’ЯЗНИЙ ГРАФ ЗА ОЙЛЕРОМ

без вершин існувати не може.

граф не має ребер

граф з n вершинами має n(n - 1)/ 2 ребер
Повний граф з n вершинами є регулярним графом степеня n - 1.
Графи K1 — K4 є планарними. Повні графи з більшою кількістю вершин не є планарними, оскільки містять підграф K5 і, отже, не задовольняють умови Куратовського.

то він називається плоским, у протилежному випадку – просторовим.

Повний граф завжди зв'язний, але не всякий зв'язний граф є повним.

або орграфом.
В орієнтованому графі для вершини 1 існує тільки два орієнтовані цикли:
(1-2, 2-5, 5-3, 3-1),
(1-4, 4-7, 7-3, 3-1).

1

2

3

4

5

6

7

несуттєвий порядок двох його кінцевих вершин

Неорієнтований граф (вершини та ребра)

істотний порядок двох його кінцевих вершин.

Орієнтований граф

називається зваженим.
Існують неорієнтовані зважені графи та орієнтовані зважені графи.

1

2

3

4

5

6

7

4

6

10

3

1

12

8

7

5

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

Змішаний граф

Змішаний граф з петлями

складається з точок (вершин графу 1,2,3,4,5,6) і ребер (ліній або відрізків №1(1-3), №2(3-4), №3(4-5), №4(3-5), №5(2-3), №6(2-5), №7(5-6), №8(6-2), №9(2-1), які сполучають деякі точки (вершини) за вибраним алгоритмом

Сутність геометричної конфігурації графа, в якому всі вершини можна обійти за маршрутом без перетинання ребер графу

саму вершину, з якої ми вийшли, обійшовши кожне з ребер тільки один раз.

Схема мостів в Кенігзберзі

б вершини ми не почали б обхід, ми не можемо обійти весь граф і повернутись назад, не проходячи жодного ребра двічі. Якби такий цикл існував, то з кожної вершини виходило б стільки ребер , скільки в неї входить , інакше кажучи степінь кожної вершини була б парним числом. Таким чином, відповідь на питання Ойлера - негативна.
Виклавши розв'язання задачі про кенігсберзькі мости, Ойлер в своїй праці поставив питання: на яких графах можна знайти цикл, який містить всі ребра графа, при чому кожне ребро зустрічається в циклі рівно один раз?
Це дало початок системному математичному підходу до побудови та вивчення властивості графів.

ланцюг, який проходить через кожне ребро.
Такий ланцюг називають ойлеровим ланцюгом, або ойлеровим циклом

Структура вершин та ребер в неорієнтованому ойлеровому графі (* - означено точку входу ойлерового ланцюга - циклу)