Історія виникнення теорії графів, їх зображення на площині. Побудова матриці інцидентності; графу, ізоморфного заданому. Ейлерів цикл та шлях у графа. Гамільтонів цикл. Алгоритм Дейкстри. Визначення рівня кожної вершини, ексцентриситет та висоту дерева.
При зображенні графів найчастіше використовується наступна система позначень: кожна вершина зображується у вигляді точки на площині, і якщо між вершинами існує ребро, то відповідні точки зєднуються відрізком. У випадку коли граф не містить циклів (шляхів однократного обходу ребер і вершин з поверненням у вихідну точку), його прийнято називати «деревом». Граф - це фігура на площині, яка складається з непорожньої скінченної множини V точок (вершин) і скінченної множини E орієнтованих чи не орієнтованих ліній (ребер), що зєднують деякі пари вершин. За теоремою Дірка «Якщо для кожної вершини V звязного простого графа n 3 вершинами, виконується нерівність deg(v) n/2, тоді цей граф має Гамільтонів цикл». Шлях до неї через 1-у вершину дорівнює найкоротшій відстані до 1-ї вершини довжина дуги між 1-ю та 2-ю вершиною, тобто 0 7 = 7.
Вы можете ЗАГРУЗИТЬ и ПОВЫСИТЬ уникальность своей работы
