Теорія графів

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

Теорія графів — розділ математики, що вивчає властивості графів. Наочно граф можна уявити як геометричну конфігурацію, яка складається з точок (вершини) сполучених лініями (ребрами). У строгому визначенні графом називається така пара множин G = (V, E), де V є підмножина будь-якої зліченної множини, а E — підмножина V × V.

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

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

Теорія графів містить велику кількість невирішених проблем і поки не доведених гіпотез.

Формальне означення графа:

Нехай X = { x1,…,xn} — деяка скінченна множина (множина вершин), M2 — множина всіх невпорядкованих пар елементів з X,

M2 = { (xi,xj): xi ∈ X, xj ∈ X, i ≠ j}


1. Граф G(X, W) — пара множин X, W ⊂ M2. Множина X — це множина вершин, множина W — це множина ребер. Якщо (xi,xj) ∈ W, то ми говоримо, що ребро (xi,xj) сполучає вершину xi з вершиною xj; інша термінологія — ребро (xi,xj) і вершини xi та xj інцидентні.

2. Граф G(X, W) називається повним, якщо W = M2.

Якщо множина X містить n вершин, то, очевидно, число ребер повного графа дорівнює Cn2. Повний граф з n вершинами позначається Kn.

3. Граф G(X, W) називається порожнім, якщо W = ∅.

4. Вершини xi та xj графа G(X, W) інцидентні, якщо (xi,xj) ∈ W.

5. Степенем d(xi) вершини xi графа G(X, W) називається число вершин xj, які інцидентні вершині xi (число відрізків, які виходять з вершини xi).

6. Якщо d(xi)=1, то вершина xi називається кінцевою вершиною графа G(X, W). Якщо d(xi)=0, то вершина xi називається ізольованою.

інші мови
አማርኛ: ሥነ ግራፍ
беларуская: Тэорыя графаў
čeština: Teorie grafů
dansk: Grafteori
Ελληνικά: Θεωρία γράφων
English: Graph theory
Esperanto: Grafeteorio
euskara: Grafo teoria
Bahasa Indonesia: Teori graf
íslenska: Netafræði
日本語: グラフ理論
한국어: 그래프 이론
lietuvių: Grafų teorija
latviešu: Grafu teorija
монгол: Графын онол
Bahasa Melayu: Teori graf
Nederlands: Grafentheorie
norsk nynorsk: Grafteori
norsk: Grafteori
português: Teoria dos grafos
sicilianu: Tiuria dî grafi
srpskohrvatski / српскохрватски: Teorija grafova
Simple English: Graph theory
slovenčina: Teória grafov
slovenščina: Teorija grafov
српски / srpski: Теорија графова
svenska: Grafteori
Türkçe: Çizge teorisi
Tiếng Việt: Lý thuyết đồ thị
中文: 图论
粵語: 圖論