Граф (математика)
Матеріал з Вікіпедії — вільної енциклопедії.
Граф — пара множин V і E, елементи множини V називають вершинами (англ. vertex), множина E містить впорядковані та невпорядковані пари вершин. Невпорядкована пара вершин називається ребром, впорядкована — дугою.
Граф, який містить тільки ребра називається неорієнтованим, який містить тільки дуги — орієнтованим. Якщо пара вершин сполучається кількома ребрами чи дугами одного напрямку, то ребра (дуги) називають кратними (паралельними). Дуга чи ребро що сполучає вершину саму із собою називається петлею. Граф без кратних дуг і петель називається простим.
Вершини сполучені ребром чи дугою називають суміжними, також називають суміжними ребра, що мають спільну вершину. Ребро (чи дуга) і її вершина називаються інцидентними. Ребро (u, v) з'єднує вершини u і v, дуга (u, v) починається у вершині u і закінчується у вершині v.
Кожен граф можна відобразити в евклідовому просторі множиною точок, які відповідають вершинам, сполучених лініями, що відповідають ребрам (дугам).
Іноді є потреба пару вершин з'єднати більше, ніж одним ребром. Мультиграфом називають пару G=(V,E), де V - множина, елементи якої називають вершинами. E — сім'я ребер, кожне з яких — це пара вершин із V.
Ребра, які з'єднують одну й ту саму пару вершин, називають кратними (перелельними) ребрами.
Мультиграф, який може мати петлі, іноді називають псевдографом.
| Тип графа | Ребра | Кратні ребра |
|---|---|---|
| Простий граф | Неорієнтовані | Ні |
| Мультиграф | Неорієнтовані | Так |
| Орієнтований граф | Орієнтовані | Ні |
| Орієнтований мультиграф | Орієнтовані | Так |
[ред.] Дивіться також
 |
Це незавершена стаття з математики. Ви можете допомогти проекту, виправивши або дописавши її. |
[ред.] Література
- J.A. Bondy, U.S.R. Murty. Graph Theory with Applications (1976), 264 c., Elsevier/North-Holland. ISBN 0-444-19451-7.
- J.A. Bondy, U.S.R. Murty. Graph Theory (2008), 654 c., Springer. ISBN 978-1-84628-969-9.
- Jungnickel, Dieter. Graphs, Networks and Algorithms (2008), 650 c., Springer. ISBN 978-3-540-72779-8.
- Сик Дж., Ли Л., Ламсдэйн Э.. C++ Boost Graph Library (2006), 304 c., Питер. ISBN 978-5-469-00352-6.
- Robert Sedgewick. Algorithms in Java, Third Edition, Part 5: Graph Algorithms (2003), 528 c., Addison Wesley. ISBN 0-201-36121-3.
