елементів, ні форма або довжина ліній не мають значення - важливо лише, які саме пари елементів з'єднані лініями. Однак, цю ж структуру можна представити і без графічного зображення, а просто перерахувавши пари пов'язаних між собою елементів: (1,4), (4,5), (5,3), (3,2), (2,1) , (1,3). Таким чином ми отримуємо два списки: список елементів і список пар елементів. Разом вони складають те, що математично називають «графом». Граф складається з двох множин - множини вершин і безлічі ребер , причому для кожного ребра вказана пара вершин, які це ребро з'єднує.
У лістингу 1 наводиться приклад реалізації даного графа ( Рис. 1.1 в ) мовою python з використанням бібліотек NetworkX і matplotLib.
Лістинг 1.
: matplotlib.pyplot as plt: networkx as nx
=nx.cycle_graph (24)=nx.spring_layout (G, iterations=200). draw (G, pos, node_color=range (24), node_size=800, cmap=plt.cm. Blues). show () # display
Існує також поняття орієнтований граф або орграф . Це є граф, ребрам якого присвоєно напрямок. Спрямовані ребрами іменуються також дугами або просто ребрами .
Тобто на Рис. 1.1 р. пара вершин (4, 5) і (5, 4) буде відрізнятися, так як ребро, яке їх з'єднує, буде мати напрямок.
Для орієнтованих графів виділяють такі поняття:
ребро входить в вершину, якщо по ньому можна рухатися в напрямку до цієї вершини , і < i align="justify"> виходить з вершини, якщо по ньому можна рухатися в напрямку від цієї вершини
входить ступінь вершини - це число входять до неї ребер;
виходить (або виходить ) ступінь вершини - це число виходять з неї ребер;
шлях з вершини A в вершину B - це послідовність ребер і проміжних вершин, за якими можна дійти з A в B; довжина шляху визначається, як звичайно (число ребер); простий шлях - як звичайно, шлях, в якому вершини (і тим більше, ребра) не повторюються;
орієнтований цикл - це замкнутий простий шлях в орієнтованому графі;
сильно зв'язний орієнтований граф - це орієнтований граф, де з будь-якої вершини в будь-яку є шлях (для кожної пари вершин A і B є як шлях з A в B, так і шлях з B в A);
компонента сильної зв'язності - це частина графа, яка сама по собі сильно связна, але її не можна розширити так, щоб вона залишилася сильно зв'язного; між різними компонентами сильної зв'язності можуть бути ребра , але всі ребра між двома різними компонентами спрямовані в одну і ту ж сторону
суміжні ребра - ребра, які мають спільну кінцеву вершину.
Вершини і називаються кінцевими вершинами (або просто кінцями ) ребра.
По відношенню до вершин ребро e в такому випадку н...
