загрузка...
загрузка...
На головну

Плоскі графи. Ейлерови графи. Гамільтови графи. орграфів

Дивіться також:
  1. плоскі графи
  2. Плоскі залізобетонні перекриття
  3. Теплопередача через плоскі одно- і багатошарові стінки.
  4. Ейлерови графи

Нехай дано непорожня множина X, Що складається з елементів, які називаються точками (x1, x2, ...), І на X задано безліч відносин T, Що дозволяють встановити відповідність між кожним елементом безлічі X і деяким його підмножиною. Кожна пара точок xi, xj безлічі X, Між якими встановлено відношення з безлічі T, називається ребром.

Визначення 1. Непорожня множина X і безліч відносин T називається графом і позначається G (X, T). Граф називається кінцевим, якщо безліч X звичайно.

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

Ребра графа позначають парою вершин (x1, x2).

Визначення 2. Вершини, які не належать жодному ребру графа, називаються ізольованими.

приклад 1. Розглянемо граф

вершини x1, x4, x5 - Ізольовані (точка перетину діагоналей не належить графу). Граф може не мати ребер. Тоді він складається з ізольованих точок.

Приклад 2. Граф

складається тільки з ізольованих точок.

Визначення 3. Дві вершини називаються суміжними, якщо вони з'єднані ребром, два різних ребра суміжні, якщо вони мають спільну вершину.

Визначення 4. Ребро і будь-яка з його вершин називаються інцидентними.

Визначення 5. Ребро графа G (X, T), у якого початкова і кінцева вершини збігаються, називається петлею.

Приклад 3.Розглянемо граф

На малюнку ребро (x3, x3) Є петлею.

Прикладами графів можуть служити схеми залізниць, автомобільних доріг, метрополітену, формули молекул, генеалогічні дерева і т. Д.

Існують різні способи завдання кінцевого графа G (X, T). нехай x1, x2, ..., xn - Вершини графа, l1, l2, ..., lm - Ребра графа.

Визначення 6. Матрицею суміжності називається матриця Аn?n, У якій елемент aij дорівнює кількості ребер, що з'єднують вершини xi і xj.

Визначення 7. Матрицею інцидентності називається матриця Вn?m, У якій елемент bij дорівнює 1, Якщо вершина xi инцидентна ребру lj, І дорівнює 0 у противному випадку.

Приклад 4.для графа

матриці суміжності і інцидентності мають вигляд

Графи можна задавати списками пар вершин, з'єднаних ребрами, або завданням для кожної вершини безлічі суміжних вершин.

Ігри з природою «-- попередня | наступна --» характеристики графа
загрузка...
© om.net.ua