Тема роботи: Представлення телекомунікаційних мереж у термінах теорії графів. Мета роботи: Навчитись представляти телекомунікаційні мережі за допомогою матриць суміжності, інцедентності та списку ребер, і оволодіти основними поняттями теорії графів. ТЕОРЕТИЧНІ ВІДОМОСТІ Визначення теорії графів: Ексцентриситет вершини — максимальна з відстаней від даної вершини до будь-якої іншої вершини. Радіус графа — мінімальний з ексцентриситетів вершин зв'язаного графа; вершина, на якій досягається цей мінімум називається центральною вершиною. Діаметр графа — максимальний з ексцентриситетів вершин зв'язаного графа. Відстань між вершинами — найменша кількість ребер шляху, що з'єднує дві вершини. ХІД РОБОТИ Запустити файл макету з розширенням .m. У вікні що відкрилось запустити макет на виконання за допомогою кнопки Run (зелений трикутник). Ознайомитись з роботою лабораторного макету. *Для збереження рисунків графів вибрати File->Print to Figure далі у створеному вікні вибрати File->Save As… та зберегти у форматі Enhanced metafile (*.emf). Навчитись працювати з матрицями суміжностей: 1) Записати (придумати) матрицю суміжності орієнтованого графа G={7,12}. Ввести її у лабораторний макет (поле ) та побудувати візуальне представлення графа. а) Чи є у побудованому графі ізольовані вершини або незв’язні компоненти? так, назвіть їх; ні, які ребра потрібно видалити щоб вони утворились? б) Чи є у графі вершини типу “глухий кут”? так, то змінивши напрямок ребер чи можна це усунути; ні, вкажіть цикл обходу всіх вершин; в) Чи існує в графі цикл обходу вершин (цикл Гамільтона)? так, вкажіть послідовність вершин, що входять до даного циклу; ні, що потрібно змінити в графі щоб даний цикл існував; г) Чи існує в графі цикл обходу ребер (цикл Єйлера); так, вкажіть послідовність ребер, що входять до даного циклу; ні, що потрібно змінити в графі щоб даний цикл існував; д) Побудувати доповнення (обернений) графа G. 2) За допомогою лабораторного макету побудувати випадковий неорієнтований граф G={7,15} та записати його матрицю суміжності. а) Як зміниться топологія графа (структурні зв’язки), якщо циклічно зсунуту вправо 2 стовпці у матриці суміжностей? б) Як зміниться топологія графа (структурні зв’язки), якщо всі елементи над або під діагоналлю перетворити в 1? Або 0? 3) За допомогою лабораторного макету побудувати випадковий орієнтований граф G={5,10} та записати його матрицю відповідностей (інцедентності). а) Як з матриці відповідностей можна визначити ступінь кожної вершини? 4) Задано граф G та M. G={(5,1), (6,1), (2,3), (3,4), (2,6), (3,6), (5,6), (1,7), (2,7), (3,7) (4,7) (6,7)} M={(2,1), (5,1), (1,2), (4,2), (5,2), (6,2), (2,4), (5,4), (6,4), (1,5), (2,5) (4,5) (6,5), (2,6), (4,6), (5,6)} Визначте: а) Записати їх матриці суміжності та побудувати графічне представлення. б) Графи орієнтовані чи неорієнтовані? в) Яка кількість вершин V та ребер E? г) Яка з вершин має найбільшу ступінь? Скільки? д) Визначте ексцентриситети вершин для графа G та M. е) Який радіус кожного з графів? є) Який діаметр кожного з графів? ж) Чи містять графи петлі (елементарні цикли)? Вкажіть послідовність ребер. з) Чи містять графи ізольовані вершини? і) При транспонування GT та MT чи змінюється графічне представлення графа? Як? ВАРІАНТИ ІНДИВІДУАЛЬНОГО ЗАВДАННЯ