Зміст
Введення
Деякі відомості з теорії графів
Способи представлення графа в інформатиці
Пошук у глибину безлічі елементарних циклів графа
Про середовищі wxDev-C + +
Розробка в wxDev-C + +
Керівництво користувачеві
Висновок
Список використаної літератури
Додаток А
Введення
В даний час дискретна математика і суміжні з нею розділи привертають велику увагу фахівців різних галузей науки і техніки, будучи ефективним апаратом формалізації сучасних інженерних задач, пов'язаних з дискретними об'єктами. Особливе значення з практичної точки зору має теорія графів, що використовується при проектуванні інтегральних схем і схем управління, дослідженні автоматів і логічних ланцюгів, при системному аналізі, автоматизованому управлінні виробництвом, при розробці обчислювальних та інформаційних мереж, у схемотехническом та конструкторсько-топологічному проектуванні, і т . д. Широке застосування теорія графів знаходить в сучасній обчислювальній техніці і кібернетиці: в теоретичному програмуванні, при проектуванні ЕОМ, баз даних, систем логічного керування. Тому основну увагу в курсовій роботі приділяється викладу основ теорії графів і алгоритмів пошуку елементарних циклів у глибину в неорієнтованих графах. br/>
Деякі відомості з теорії графів
У теорії графів об'єкти представляються як вершіниграфа, а зв'язки - як дуги, або ребра. Граф або неорієнтоване графG (рис.1) - це впорядкована пара <# "225" src = "doc_zip1.jpg"/>
Рисунок 1 неорієнтовані граф
Вершини і ребра графа називаються також елементами графа, число вершин у графі | V | - порядком, число ребер | E | - розміром графа.
Вершини u і v називаються кінцевими вершинами (або просто кінцями) ребра e = {u, v}. Ребро, у свою чергу, з'єднує ці вершини. Дві кінцеві вершини одного і того ж ребра називаються сусідніми. p> Два ребра називаються суміжними, якщо вони мають спільну кінцеву вершину.
Два ребра називаються кратними, якщо безлічі кінцевих вершин збігаються.
Ребро називається петлею, якщо його кінці збігаються, тобто e = {v, v}.
Орієнтований граф (скорочено орграф) G (рис.2) - це впорядкована пара <# "justify">
Малюнок 2 Орієнтований граф
Дуга - це впорядкована пара вершин (v, w), де вершину v називають початком, а w - кінцем дуги. Можна сказати, що дуга веде від вершини v до вершини w.
Шляхом (або ланцюгом) у графі називають кінцеву послідовність вершин, в якій кожна вершина (крім останньої) з'єднана з наступною в посл...
