Головна | Про нас | Зворотній зв'язок
Довідка по ІДЗ «Графи»
Скелет графа загального вигляду. У разі, коли при дослідженні графа L = (XU; P) загального вигляду потрібно не повна інформація про нього, а лише знання того, які пари його різних вершин суміжні і які ні, вдаються до носія такої інформації - скелету графа L, який позначимо як. Граф відноситься до класу звичайних графів з безліччю вершин тим же, що і в графі L, і новим безліччю ребер. певним наступним чином:
1) якщо в графі L є петлі, то вони видаляються;
2) якщо в графі L є дуги, то проводиться дезорієнтація дуг;
3) якщо в графі L є кратні ребра, то вони замінюються одним еквівалентним ребром-ланкою;
4) залишилися ребра утворюють безліч ребер.
Таким чином, безліч ребер складається з ребер, отриманих з безлічі U після виконання описаних вище процедур 1, 2, 3.
Визначення числа маршрутів довжини «L» на графі
Маршрутом mi, j в графі G = (X, U) називається кінцева послідовність вершин і ребер виду -
де x0. xl - відповідно початкова і кінцева вершини маршруту m0, l.
Очевидно, в кінцевому графі G = (X, U) можна виділити тільки кінцеве число маршрутів. Довжина маршруту mi, j дорівнює числу ребер, які в нього входять.
Часто потрібно знати, скільки маршрутів заданої довжини в графі G пов'язує вершину xi з вершиною xj.
Для визначення маршрутів довжини q в графі G = (X, U) його матрицю суміжності R зводять до рівня, що дорівнює q. Тоді для кожного значення ступеня q = 1,2, ..., k значення елемента (ri, j) q матриці R q визначає кількість маршрутів mi, j довжиною, що дорівнює значенню ступеня q.
ПРИКЛАД. Для графа G = (X, U). представленого на малюнку 3, визначити кількість маршрутів довжини, що дорівнює 2.
Матриця суміжності R графа G має вигляд: