Научная работа: Розвязування задач за допомогою графів

Вершина графа. Або кінець якого-небудь ребра графа, або ізольована точка графа.

Гамільтонова лінія. Елементарний цикл, що проходить по всіх вершинах графа.

Грань багатокутного графа G. Частина площини, обмежена яким-небудь мінімальним циклом G або максимальним циклом C1 графа G; у останньому випадку це частина площини, що лежить поза С1; її називають також нескінченною гранню.

Степінь р(А) вершини A. Число ребер, що сходяться у вершині A. Для орієнтованого графа р(А) означає кількість ребер, що виходять, а р*(А) - кількість вхідних ребер у вершину A; в цьому випадку є два степені.

Ребро графа. Крива, що сполучає дві вершини графа і що не містить інших вершин.

Граф G*, подвійний багатокутному графові G. Багатокутний граф, кожна вершина якого відповідає певній грані графа G, а кожна грань - певній вершині графа G. Дві вершини графа G* сполучено ребром в тому і лише у тому випадку, коли відповідні грані графа G мають загальне ребро.

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

Додекаедр. Многогранник, обмежений 12 п'ятикутними гранями.

Доповнення G графа G. Граф G+ складається зі всіх ребер (і їх кінців), які необхідно додати до G для того, щоб вийшов повний граф.

Ізольована вершина. Вершина, з якої не виходитиме жодного ребра.

Плоский граф. Граф, якого можна накреслити на площині так, щоб його ребра перетиналися тільки в його вершинах.

Ізоморфні графи. Графи G1 і G2 ізоморфні, якщо між їх вершинами можна встановити таку взаємно однозначну відповідність, що пари вершин графа G1 в тому і лише в тому разі сполучені ребром, коли сполучені ребром відповідні пари вершин графа G2. У випадку орієнтованих графів ця відповідність повинна зберігати орієнтацію ребер.

Ікосаедр. Многогранник, обмежений 20 трикутними гранями.

Інцидентність ребра і вершини. Ребро називається інцидентним вершині, якщо вона є одним з його кінців.

Корінь дерева. Будь-яка вершина, яку ми вибираємо за початкову точку дерева.

Кратні ребра. Якщо дві вершини графа сполучено більш ніж одним ребром, то кожне таке ребро називається кратним.

Ліс. Граф. всі зв'язні компоненти якого є деревами (граф без циклів).

Максимальний цикл С1 многокутного графа G. Цикл, що оточує весь граф G.

Мінімальний цикл многокутного графа G. Цикл, утворений граничними ребрами одного з багатокутників, складових G.

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

Непарна вершина. Вершина, степінь якої непарний.

Зворотний граф G* для даного орієнтованого графа G. Граф G* виходить з G через зміну напрямів всіх його ребер.

Однорідний граф степеня r. Граф, степені всіх вершин якого однакові і рівні r

Октаедр. Многогранник, обмежений 8 трикутними гранями.

Орієнтований граф. Граф, на якому вказані напрями всіх його ребер.

Перешийок. Інший термін, для зв'язуючого ребра.

Петля. Ребро графа, обидва кінці якого збігаються.

Повний граф. Граф, будь-які дві вершини якого сполучено ребром. Повний граф, у якого n вершин, має

½n(n - 1) ребер.

К-во Просмотров: 278
Бесплатно скачать Научная работа: Розвязування задач за допомогою графів