інтерес характер поведінки власних значень при деяких перетвореннях графів, особливо в тих випадках, коли спектр складного графа можна виразити в термінах спектрів елементарних графів.
1.2 ОСНОВНІ ПОНЯТТЯ І ПОЗНАЧЕННЯ
Наведемо ще кілька теоретико-графових понять, часто вживаних в даний роботі, а також введемо деяку типову систему позначень і пояснимо суть окремих угод, які використовуються надалі.
Кажуть, що граф Н=(У, V) є подграфом графа G=(Х, U), якщо YX і V U. Граф Н називається остовне подграфом або частковим графом графа G, якщо У=Х. Якщо безліч V складається з усіх тих ребер безлічі U, які з'єднують вершини з множини У, то Н називається породженим подграфом. Іноді кажуть, що породжений підграф покривається власними вершинами, а частковий підграф покривається власними ребрами.
Число ребер, інцидентних даній вершині неорієнтованого графа, називається ступенем або валентністю цієї вершини. Зауважимо, що неорієнтовану петлю вважають двічі, і, отже, її внесок у валентність вершини, до якої вона приєднана, дорівнює 2. Якщо всі вершини графа мають одну і ту ж валентність, рівну r, то граф називається регулярним ступеня r.
У орграфа будемо проводити розходження між полустепені заходу або задньої валентністю і полустепені результату або передньої валентністю вершини, що вказують відповідно число дуг, які заходять в дану вершину, і число дуг, які з неї виходять.
Якщо дуга спрямована з вершини х до вершини у, то запис має вигляд; х і у називаються сусідніми вершинами, причому х є заднім сусідом вершини у, а у - переднім сусідом вершини х.
Контур довжини n (позначається) - це орграф з безліччю вершин {x1 ..., хn}, у якого дyгaмі є (хi, хi + l), i=1, ..., n - 1, і (хn, x1). Лінійний орієнтований граф - це орграф, в якому полустепені результату і заходу кожної вершини рівні 1, т. Е. Він складається з контурів.
остовно лінійний подграф мультиграфом (мультіорграфа) G, т. е. лінійний підграф графа G, що містить всі його вершини, іноді називають лінійним фактором графа G. Лінійний фактор мультиграфом складається з непересічних копій К2.
Регулярний остовно подграф ступеня s мультиграфом G називається фактором (регулярним) ступеня s, або, коротше, s-фактором графа G.
Будь-яка послідовність наступних один за одним ребер (дуг) мультиграфом (мультіорграфа в напрямку їх орієнтації) називається мaршрут. Довжина маршруту - це число його ребер (дуг). Маршрут може містити одне і те ж ребро (дугу) більш ніж один раз.
Простий ланцюг Рn довжини n - 1, n? 2, - це граф, що має n вершин х1, ..., хn і n - 1 ребер, в якому вершини хi, і хi + l, i=1, ... ..., n - 1. з'єднані ребром.
мультиграфом (мультіорграф) називається зв'язковим (сильно зв'язковим), якщо будь-які його дві вершини з'єднані простий ланцюгом (маршрутом). В іншому випадку мультіграф називається незв'язним і складається з двох і більше частин, які називаються компонентами; дві вершини незв'язного графа належать різним компонентам, якщо вони не з'єднуються ніякої простий ланцюгом.
Довжина найкоротшою простий ланцюга між двома вершинами називається відстанню між цими вершинами. Діаметр зв'язкового мультиграфом - найбільше з відстаней між його вершинами.
Простий цикл Сn довжини n - це регулярний зв'язний граф степеня 2, що має n вершин. Розглядаючи його як підграф, можна говорити, що С1 - петля, С2 - пара кратних ребер, СЗ - трикутник, С4-чотирикутник. Обхват мультиграфом (мультіорграфа) - довжина його найкоротшого простого циклу (контуру).
мультиграфом G називається правильно розфарбованим, якщо його суміжні вершини мають різні кольори. Граф G є k-розфарбовуваним, якщо його можна правильно розфарбувати k квітами. Хроматичної число графа G дорівнює k, якщо G k-розфарбовуємо і не є (k - l) -раскрашіваемим. Граф G називається дводольним, якщо його хроматичної число одно 1 або 2. Безліч вершин двудольного мультиграфом G можна розбити на дві частини, наприклад Х і У, таким чином, щоб кожне ребро графа G єднало вершину з Х з деякою вершиною з У. Іноді граф G будемо позначати як G=(Х; У; U), де U - безліч ребер графа. Якщо G - зв'язний граф, що має принаймні одне ребро, то Х і У не порожні і граф G визначається однозначно (з точністю до позначень). Якщо вершини позначені таким чином, що
Х={x1, x2, ..., XТ}, Y={XТ + l, XТ + 2, ..., XТ + n},
то матриця суміжності графа G буде мати вигляд
,
де В - nт-матриця, а ВТ - матриця, транспонована до матриці В.
мультиграфом називається полурегулярних ступенів r1, r2 (можливо r1=r2) якщо він двочастковий, кожна його вершина має ступінь r1ілі r2. І кожне ребро з'єднує деяку вершину ступеня r1 з деякою вершиною ступеня r2.
Повний n-вершинний граф Кn - це граф, будь-які дві вершини якого з'єднані ребром. Повний дводольний граф з n + т вершинами ...
