Дискретна математика

геометричні графи

Глава про графах починалася з розповіді про деяких малюнках і схемах, які Д. Кеніг запропонував називати графами. Проте, в попередньому пункті, де давалися визначення поняття графа, малюнки або схеми навіть не згадувалися. Справа в тому, що вище йшлося про так званих абстрактних графах, а малюнки і схеми являють собою геометричні графи. Ці два поняття хоча і дуже близькі, але, тим не менш, різні.

Визначення 4.3.Геометріческій граф- це сукупність. де - непорожня безліч точок простору, а - безліч простих кривих (можливо, спрямованих), що задовольняють наступним умовам:

1. кожна замкнута крива безлічі містить тільки одну точку безлічі;

2. кожна незамкнута крива безлічі містить рівно дві точки множини. які є її граничними точками;

3. криві безлічі не мають спільних точок, за винятком точок з множини.

Елементи безлічі називають вершинами графа, а саме це безліч - носієм графа; елементи безлічі називаються ребрами графа, а саме - його сигнатурою.

Таким чином, геометричний граф є просто геометрична конфігурація або структура в просторі, що складається з безлічі точок, взаємопов'язаних безліччю простих (не мають точок самопересеченія) кривих. На рис. 4.1 зображені два геометричних графа.

Очевидно, що вершини будь-якого абстрактного графа можна представити точками простору, а його ребра ототожнити з деякими простими кривими, що з'єднують кінці цих ребер. Тому будь-який абстрактний граф завжди еквівалентний (по відношенню до властивостей, що вивчаються в теорії графів) деякого геометричного графу. Геометричний граф, еквівалентний в зазначеному вище сенсі абстрактного графу, будемо називати зображенням цього абстрактного графа. Таким чином, геометричні графи можна розглядати як зручне і наочне уявлення абстрактних графів, а не просто як окремий випадок. Відзначимо тільки, що існує величезна кількість варіантів розташування вершин геометричного графа в просторі і не менша кількість способів накреслення його ребер. Отже, у абстрактного графа можуть бути різні по виду зображення, на перший погляд абсолютно не схожі один на одного. Обидва графа на рис.4.1 є зображеннями абстрактного графа з прикладу 4.1. Не схожі і три зображення абстрактного графа, показані на рис. 4.2.

До речі, граф на рис.4.2 є неорієнтований дублікат орграфа (рис. 4.3).

Хоча багато графи, що представляють реальні об'єкти, є геометричними графами, з точки зору теорії графів їх єдина структурна особливість полягає в тому, що з кожним геометричним ребром пов'язані дві (можливо, збігаються) геометричні вершини. Теорія графів побудована з урахуванням саме цю особливість і не враховує реальної природи вершин і ребер. Таким чином, нумерація вершин і ребер з фіксацією вершин кінців кожного ребра і зазначенням його орієнтації (в тих випадках, коли це необхідно) містить всю інформацію, достатню для опису і геометричного графа, і абстрактного графа. Всі поняття і визначення, введені вище для абстрактних графів, справедливі і для їх зображень, тобто для геометричних графів.

Зауважимо, що введення абстрактного графа дозволяє не тільки позбутися від випадкових геометричних характеристик, зберігши найважливіші комбінаторні властивості графа. Воно розширює можливості застосування теорії, так як багато реальні структури мають комбінаторні властивості, які зручно розглядати як граф. Наприклад, у вигляді графа можна задати співвідношення між окремими роботами, які становлять складні проекти. В цьому випадку ребра, після того як задана їх орієнтація, представляють окремі роботи, а вершини відображають послідовність їх виконання.

зважені графи

Наступний крок в описі зв'язків між об'єктами з допомогою графів полягає в приписуванні ребрах деяких кількісних значень, якісних ознак або характерних властивостей, званих вагами. У найпростіших випадках це може бути порядкова нумерація ребер, яка вказує на черговість їх розгляду (пріоритет або ієрархія). Вага ребра може означати довжину (шляхи сполучення), пропускну здатність (лінії зв'язку), напруга або струм (електричні ланцюги), кількість набраних очок (турніри), валентність зв'язків (хімічні формули), кількість рядів руху (автомобільні дороги), колір провідника ( монтажні схеми електронного пристрою), характер відносини між людьми (син, батько, підлеглий, вчитель) і т. п.

Вага можна приписувати не тільки ребрах, але і вершин. Наприклад, вершини, відповідні населеним пунктам, можуть характеризуватися кількістю місць в готелях, пропускною спроможністю станцій техобслуговування. Взагалі, вага вершини означає будь-яку характеристику відповідного їй об'єкта - атомна вага елемента в структурній формулі, колір зображуваного вершиною предмета, вік людини і т. П.

Визначення 4.4. Графи, вершин і (або) ребрах яких приписані деякі ваги, називають зваженими графами. Графи, вершини яких пронумеровані, ще називають поміченими графами.

Особливе значення для моделювання фізичних систем придбали зважені орієнтовані графи, звані графаміпотоковсігналов або сігнальниміграфамі. Вершини сигнального графа ототожнюються з деякими змінними, що описують стан системи, а вага кожної вершини означає функцію часу або деякої величини, що характеризує відповідну змінну (сігналвершіни). Дуги відображають зв'язки між змінними, і вага кожної дуги являє собою чисельну або функціональне відношення, що задає передачу сигналу від однієї вершини до іншої (передачадугі). Сигнальні графи знаходять широке застосування в теорії ланцюгів і систем, а також у багатьох інших областях науки і техніки.

ступені вершин

Нехай - неорієнтований граф.

Визначення 4.5.Степенью вершини графа будемо називати число. дорівнює кількості ланок графа, інцидентних вершині. Вершина графа, що має ступінь 0, називається ізольованою. а ступінь 1 - висячої.

При підрахунку ланок, інцидентних вершині. деяку невизначеність вносять петлі, так як їх можна вважати і як єдине, і як подвійне ланка. Залежно від розглянутої задачі, може виявитися більш зручним як той, так і інший спосіб підрахунку. Щоб не виникали непорозуміння, слід в кожному випадку вказувати, вважається петля одноразовим ланкою або подвійним.

Число. яка дорівнює кількості ланок, що з'єднують вершини і. назвемо кратністю цих вершин. Якщо у графа немає кратних ланок, то чи. при цьому у неорієнтованих графів.

У графа, представленого на рис. 4.4, = 1 (висяча вершина), = 0 (ізольована вершина) і = 2, якщо вважати петлю одноразовим ланкою. При цьому . а.

Випишемо кілька простих формул. Очевидно, що ступінь будь-якої вершини графа дорівнює сумі кратності всіх пар вершин. .

Так як кожне ланки графа береться до уваги при обчисленні ступенів обох його кінців, то число ланок графа пов'язано зі ступенями і кратністю його вершин співвідношенням (лема про рукостисканні):

Ці формули справедливі і при наявності у графа петель, якщо тільки при підрахунку ступенів вершин петлі вважати двічі. З останньої формули випливає, що сума ступенів усіх вершин Неограф завжди парна, отже,

Сума в лівій частині цієї формули, природно, залишиться парному навіть в тому випадку, коли відкидаються всі парні ступеня вершин. Тому справедлива наступна теорема.

Теорема 4.1. В кінцевому графі число вершин з непарної ступенем завжди парне.

Це твердження встановлено Ейлером і є історично першою теоремою теорії графів.