Поняття графа як структури даних.

Граф — це сукупність об'єктів із зв'язками між ними.

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

Велика кількість структур, які мають практичну цінність в математиці та інформатиці, можуть бути представлені графами. Наприклад, будову Вікіпедії можна змоделювати за допомогою орієнтованого графу, в якому вершини — це статті, а дуги (орієнтовані ребра) — посилання на інші статті.

Граф зі шістьма вершинами та сімома ребрами.

Першою працею з теорії графів як математичної дисципліни вважають статтю Ейлера (1736), у якій розглядалася задача про Кенігсбергські мости. Наступний імпульс теорія графів отримала близько 100 років потому з розвитком досліджень по електричним мережам, кристалографії, органічній хімії та іншим наукам.

Граф або неорієнтований граф G — це впорядкована пара G: = (V,E), для якої виконуються наступні умови:

V— множина вершин або вузлів,

E— множина пар (у випадку неорієнтованого графу — невпорядкованих) вершин, які називають ребрами.

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

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

<== попередня сторінка	\|	наступна сторінка ==>
Множини. Опис множин, операції над множинами.	\|	Орієнтований граф

Не знайшли потрібну інформацію? Скористайтесь пошуком google:

Генерація сторінки за: 0.003 сек.