Анотація
У даній пояснювальній записці наведений опис програми формування матриці суміжності по заданому списку околиць вершин орієнтованого графа і робота з цим графом, формування динамічного списку дуг орієнтованого графа по заданому списку околиць. Програма написана на мові C + + в інтегрованому середовищі розробки Microsoft Visual Studio 2005. Так само в даній пояснювальній записці представлені результати роботи програми, проведено аналіз тимчасової і ємнісний складності алгоритму. br/>
Зміст
матриця суміжність вершина граф алгоритм
Анотація
Зміст
. Теоретична частина
. Програмна частина
. Аналіз тимчасової і ємнісний складності
. Висновок
. Список використаної літератури
. Рішення контрольних прикладів
. Вихідний код програми
1. Теоретична частина
Графом називається пара (X, U), де X - кінцеве безліч вершин, а U - набір невпорядкованих і впорядкованих пар вершин. Позначимо граф G = (X, U). Неупорядкована пара вершин називається ребром, упорядкована - дугою. Граф, який містить лише ребра, називається неорієнтованим, тільки дуги - орієнтованим, або орграфом. br/>В
Якщо вершини v і u з'єднані ребром e, то говорять, що вони суміжні між собою, а ребро e інцидентне кожної з них. Кількість ребер графа, інцідентних вершині v називається ступенем даної вершини. Для орієнтованого графа виділяють вхідну ступінь, рівну кількості вхідних ребер і вихідну ступінь, рівну кількості вихідних ребер, а ступенем вершини в такому випадку називають суму її вхідної та вихідної ступеня. Вершини, які мають ступінь 0, називають ізольованими. <В
Для орграфа на рис.3 входять ступеня вершин 1,2,3,4,5 рівні відповідно 0,1,1,1,0, вихідні - 2,0,0,1,0. Ступені вершин, одержувані складанням вхідних і вихідних ступенів дорівнюють 2,1,1,2,0. Таким образів, вершина 5 - ізольована. p align="justify"> Ребро, що з'єднує вершину саму з собою, називається петлею. Якщо одну пару вершин з'єднують два або більше ребер, то такі ребра називають кратними. Граф називається простим, якщо він не містить ні петель, ні кратних ребер, інакше граф називається мультиграфом. (В деяких джерелах граф із кратними ребрами називають мультиграфом, з петлями - псевдографом). Простий граф, будь-яка пара вершин якого з'єднана ребром, називається повним. p align="justify"> Граф називається розрідженим, якщо загальна кількість ребер значно менше їх можливої вЂ‹вЂ‹кількості. Інакше граф називається щільним. br/>В
2. Програмна частина
Загальні відомості
Програма формування матриці суміжності по заданому списку околиць вершин орієнтованого графа напи...
