Метричні характеристики графа

[ виправити ] текст може містити помилки, будь ласка перевіряйте перш ніж використовувати.

скачати

МІНІСТЕРСТВО АГЕНСТВО ДО ОСВІТИ РОСІЙСЬКОЇ ФЕДЕРАЦІЇ
Державна освітня установа вищої професійної освіти «Воронезький Державний Технічний Університет» (ГОУВПО «ВДТУ»)
Кафедра: Вищої математики та фізико-математичного моделювання
Курсова робота
з дисципліни «Математика»
«Метричні характеристики графа»
Виконав: студент групи
РК-051 Жіщенко С.А.
Керівник: Ускова Н.Б.
Оцінка:
Дата захисту:
Воронеж 2006

МІНІСТЕРСТВО АГЕНСТВО ДО ОСВІТИ РОСІЙСЬКОЇ ФЕДЕРАЦІЇ
Державна освітня установа вищої професійної освіти «Воронезький Державний Технічний Університет» (ГОУВПО «ВДТУ»)
Кафедра: Вищої математики та фізико-математичного моделювання
Завдання на курсову роботу з дисципліни «Математика»
Виконавець: Жіщенко С.А.
Керівник: Ускова Н.Б.
«Метричні характеристики графа»
Тема курсової роботи затверджена постановою по РТФ від 3.10.06, № 6.
Завдання: дано два графа, побудувати їх матриці суміжності і інцидентності, визначити їх метричні характеристики.
Термін видачі курсової роботи:
Термін здачі:
Завдання прийняв ст. гр. РК-051 Жіщенко С.А.
Руководітель__________
Воронеж, 2006.

Зміст
Поняття «граф ».............................................. ............................................ 5
Матричне подання графів ............................................... ............. 9
Операції над графами ............................................... ............................... 11
Маршрути, ланцюги, цикли ............................................. ............................... 12
Метричні характеристики графа ............................................... .......... 15
Додаток теорії графів у різних галузях науки і техніки ... 16
Практична частина ................................................ .................................... 18
Лістинг програми ................................................ ................................... 21

ПОНЯТТЯ "ГРАФ"
Нехай V - непорожня множина, V (2) - множина всіх його двоелементний підмножин. Пара (V, E), де E - довільна підмножина безлічі V (2), називається графом (неорієнтованим графом). Елементи множини V називаються вершинами графа, а елементи множини E - ребрами. Отже, граф - це кінцеве безліч V вершин і безліч E ребер, E ⊂ V (2).
Термін «граф» вперше з'явився в книзі видатного угорського математика Д. Кеніга в 1936 р., хоча початкові задачі теорії графів походять ще до Ейлера (XVIII ст.).
Безлічі вершин і ребер графа G позначається відповідно VG і EG. Вершини і ребра графа називаються його елементами. Число | VG | вершин графа G називається його порядком і позначається | G |.
Якщо | G | = n, | EG | = m, то граф називають (n, m)-графом.
Кажуть, що дві вершини u і v графа суміжні, якщо множина {u, v} є ребром, і не суміжні в іншому випадку. Якщо e = {u, v} - ребро, то вершини u і v називають його кінцями. У цій ситуації говорять також, що ребро e з'єднує вершини u і v.
Два ребра називаються суміжними, якщо вони мають загальний кінець.
Вершина v і ребро e називають iнцидентною, якщо v є одним з кінців ребра e, і не iнцидентна в іншому випадку.
Зауважимо, що суміжність є відношення між однорідними елементами графа, тоді як инцидентность є відношенням між різнорідними елементами.
Безліч всіх вершин графа G, суміжних з деякою вершиною v, називається оточенням вершини v і позначається NG (v) або просто N (v).
Графи зручно зображувати у вигляді малюнків (геометричних графів). Геометричний граф у просторі n-мірному евклідовому просторі ε n є безліч точок простору ε n і безліч E простих кривих, таких: 1) що кожна замкнута крива в E містить тільки одну точку v безлічі V, 2) кожна незамкнута крива в E містить рівно дві точки безлічі V, які є її граничними точками; 3) криві в E не мають спільних точок крім точок з безлічі V. При цьому точки безлічі V відповідають вершин графа, а що з'єднують пари точок лінії - ребрах.
Граф G називається повним, якщо будь-які дві його вершини суміжні. Повний граф порядку n позначається Kn.
Граф називається виродженим (порожнім), якщо будь-які дві його вершини суміжні (тобто у нього немає ребер).
Нехай G і H графи, а φ: VG → VH - біекція. Якщо для будь-яких вершин u і v їхні образи φ (u) і φ (v) суміжні в H тоді й тільки тоді, коли u і v суміжні в G, то ця біекція називається ізоморфізмом графів G і H, асами графи G і H - ізоморфними. Ізоморфні графи будемо позначати G ≅ H (атакож H G).
Якщо граф G ізоморфний геометричному графу G ', то G' називається геометричної реалізацією графа G.
Очевидно, що відношення ізоморфізму графів є еквівалентністю. Отже, множина всіх графів розбивається на класи так, що графи з одного класу попарно ізоморфні, а графи з різних класів не ізоморфні. Ізоморфні графи природно ототожнювати, тобто вважати співпадаючими (їх можна зобразити одним малюнком). Вони могли б різнитися конкретною природою елементів, але саме це ігнорується при введенні поняття "граф".
У деяких ситуаціях все ж таки доводиться розрізняти ізоморфні графи, і тоді корисно поняття "поміченого графа". Граф порядку n називається поміченим, якщо його вершин присвоєні деякі мітки, наприклад 1, 2, ..., n. Ототожнивши кожну з вершин графа з її номером (і, отже, безліч вершин - з безліччю чисел {1, 2, ..., n}), визначимо рівність помічених графів G і H одного і того ж порядку: G = H тоді й тільки тоді, коли EG = EH.
При необхідності підкреслити, що розглянуті графи розрізняються лише з точністю до ізоморфізму, кажуть: "абстрактний граф".
Іноді розглянуте вище поняття "граф" виявляється недостатнім і доводиться розглядати більш загальні об'єкти, в яких дві вершини можуть з'єднуватися більш ніж одним ребром. Так виникає поняття "мультіграф". Мультіграф - це пара (V, E), де V-непорожнє безліч (вершин), а E-сімейство підмножин безлічі V (2) (ребер). Вживання терміну "сімейство" замість "безліч" означає, що елементи множини V (2) можуть в E повторюватися, тобто допускаються кратні ребра.
Подальше узагальнення полягає в тому, що крім кратних ребер допускаються ще петлі, тобто ребра, що сполучає вершину саму з собою. Псевдограф - це пара (V, E), де V-непорожнє безліч (вершин), а E-деяке сімейство невпорядкованих пар (ребер), не обов'язково різних.
Вивчаються також орієнтовані графи. Тоді безліч V (2) замінюється декартовим квадратом V 2, що складається з упорядкованих пар елементів множини V. Орієнтований граф (або орграф) - це пара (V, A), де V-безліч вершин, A-безліч орієнтованих ребер, які називаються дугами, A V 2.
Якщо a = (v1, v2) - дуга, то вершини v1 і v2 називаються її початком і кінцем відповідно.
Аналогічно неорієнтованому визначається орієнтований мультіграф. Розглядаються також змішані графи, у яких є і дуги, інеоріентірованние ребра. Замінюючи кожну пару (u, v) з множини E, орієнтованого (або змішаного) графа G невпорядкованою парою {u, v}, що складається з тих самих елементів uі v, отримуємо асоційований з G = (V, E) графом псевдограф H = ( V, E 0). Також кажуть, що граф H є підстава графа G.
Орграф називається турніром, якщо його підстава є повним графом.
Для всіх розглянутих узагальнень поняття "граф" аналогічно вводиться поняття ізоморфізму як біекціі між множинами вершин, що зберігає суміжність, кратності ребер, петлі та напрямки дуг.


Рис.3. Граф Петерсена



Нехай G - граф, w: EG → R + дійснозначних функція, яка ставить у відповідність кожному ребру e невід'ємне число w (e) - вага ребра e. Пару (G, w) назвемо зваженим графом. Під вагою будь-якого подграфа (можливо, невласного) зваженого графа будемо розуміти суму ваг його ребер.
МАТРИЧНІ діаграм
Нехай G-позначений граф порядку n, VG = {1, 2, ... , N}. Визначимо бінарну nЧn-матрицю A = A (G), поклавши

A (G) називається матрицею суміжності графа G. Це симетрична матриця з нулями на діагоналі. Кількість одиниць в рядку дорівнює ступеня відповідної вершини.
Очевидно, що відповідність G → A (G) визначає біекцію безлічі помічених графів порядку n на безліч бінарних симетричних nЧn-матриць з нульовою діагоналлю.
Аналогічно визначаються матриці суміжності A мульти-і псевдографов: ik дорівнює числу ребер, що з'єднують вершини i та k (при цьому петля означає два ребра).
Також визначається матриця суміжності A (G) орієнтованого графа.
Очевидно, що якщо A (G) - матриця суміжності орграфа G порядку n, то

тобто число одиниць в i-му рядку матриці A (G) дорівнює полустепені результату i-ї вершини, а число одиниць у k-му стовпці одно полустепені заходу k-ої вершини.
Теорема. Графи ізоморфні тоді і тільки тоді, коли їх матриці суміжності виходять один з одного однаковими перестановками рядків і стовпців.
Теорема вірна також для мультиграфом, псевдографов і орграфів.
Нехай G - (n, m)-граф, VG = {1, 2, ... , N} EG = {e1, e2, ... , Em}. Визначимо бінарну nЧm-матрицю I = I (G) умовами

Матриця I називається матрицею інцидентності графа G. У кожному її стовпці рівно дві одиниці, рівних стовпців немає. Як і вище, відповідність G → I (G) є біекціей безлічі помічених (n, m)-графів з занумеровані ребрами на безліч nЧm-матриць, що задовольняють описаним умов.
Матриця інцидентності I для орграфа:

Теорема. Графи ізоморфні тоді і тільки тоді, коли їх матриці інцидентності виходять один з одного довільними перестановками рядків і стовпців.
Теорема вірна також для мультиграфом, псевдографов і орграфів.
Властивості матриць суміжності і інцидентності:
1) Сума елементів матриці A (G), де G = (V, E) - мультіграф, V = {v1, v2, ..., vn}, по i-йстроке (або по i-му стовпцю) дорівнює δ ( vi). 2) Сума елементів матриці A (G), де G = (V, E) - орієнтований псевдограф,
V = {v1, v2, ... , Vn}, по i-йстроке і по i-му стовпцю відповідно рівні δ (vi), δ (vi).
3) Нехай G-орієнтований мультіграф на непустому безліччю дуг. Тоді: а) сума рядків матриці I (G) є нульовою рядком; б) будь-який рядок матриці I (G) є лінійною комбінацією інших рядків, в) ранг матриці I (G) не перевершує n-1; г) для будь-якого контуру матриці Gсумма стовпців матриці I (G), відпо-чих дуг, що входять в цей контур, дорівнює нульовому стовпцю.
4) Нехай G-мультіграф на непустому безліччю ребер. Тоді при покоордінат-ном складання по модулю 2: а) сума рядків матриці I (G) є нульовою рядком; б) будь-який рядок матриці I (G) є сумою інших рядків, в) для будь-якого циклу в Gсумма стовпців матриці I (G) , відповідних реб-рам, що входять в цей цикл, дорівнює нульовому стовпцю.

ОПЕРАЦІЇ над графою
Граф H називається подграфом графа G, якщо VH VG, EH EG. Якщо H - під-граф графа G, то говорять, що H міститься в G. Підграф називається власним, якщо він відрізняється від самого графа.
Підграф H називається остовних подграфом графа G, якщо VH = VG.
Якщо безліч вершин подграфа H є U, а безліч його ребер збігається з безліччю всіх ребер графа G, обидва кінці яких належать U, то H називається подграфом, породженим безліччю вершин U, і позначається G (U).
Якщо безліч ребер подграфа H є E ' EG, а безліч його вершин збігається з безліччю всіх кінців ребер з E 'вершин графа G, то підграф H називається подграфом, породженим безліччю ребер E' і позначається G (E ').
Нехай v - вершина графа G. Тоді операцію побудови графа H = G-v називають видаленням вершини v. Побудований в результаті цієї операції граф H містить всі ребра множини Еg крім інцидентних вершині v, а VH = VG \ {v}.
Нехай e - ребро графа G. Тоді операцію побудови графа H = G-e називають видаленням ребра e. Побудований в результаті цієї операції граф H містить всі вершини графа G, а EH = EG \ {e}.
Видалення вершини або ребра, а також перехід до підграфу - це операції, за допомогою яких можна з наявного графа отримувати інші графи з мен-шим числом елементів.
Розглянемо тепер операції, що дозволяють отримувати з наявних графів графи з великим числом елементів.
Якщо вершини u і v графа G = (VG, EG) не суміжні, то говорять, що граф H = (VH, EH) отримано з графа G додаванням ребра e = {u, v}, якщо VH = VG і EH = EG {e}, то пишуть H = G + e.
Граф H називається об'єднанням (або накладенням) графів F і G, якщо H = VF ∩ VG і EH = EF ∩ EG. У цій ситуації пишуть H = F ∩ G. Об'єднання F ∩ G називається диз'юнктивні, якщо V F ∩ V G = ∅. Аналогічно визначаються об'єднання і диз'юнктивні об'єднання будь-якого безлічі графів, причому в останньому випадку ніякі два з об'єднуються графів не повинні мати спільних вершин.
Нехай G1 = (V1, E1) і G2 = (V2, E2). Тоді твором графів (позначається G1ЧG2) називається такий граф G, для якого VG = V1ЧV2-декартово произведе-ня множин вершин вихідних графів, а EG визначається наступним чином: вершини (u1, u2) і (v1, v2) суміжні в графі G тоді і тільки тоді, коли u1 = v1, а u2 і v2 суміжні в G2, або u2 = v2, а u1 і v1 суміжні в G1
МАРШРУТИ, ЛАНЦЮГА, ЦИКЛИ
Чергується послідовність v1, e1, v2, e2, ... , En, vn +1 вершин і ребер графа така, що ei = vivi +1 (i = 1, n), називається маршрутом, що з'єднує вершини 1 і vn +1 (або (v1vn +1)-маршрутом). Очевидно, що для завдання маршруту в графі досить задати послідовність v1, v2, ..., vn +1. його вершин, або послідовність e1, e2, ... , En його ребер.
Вершина v називається досяжною з вершини u, якщо існує (u, v)-маршрут. Будь-яка вершина вважається досяжною з себе самої.
Маршрут називається ланцюгом, якщо всі його ребра різні, і простий ланцюгом, якщо всі його вершини, крім, можливо, крайніх, різні. Маршрут (1) називається циклічним, якщо v1 = vn +1. Циклічна ланцюг називається циклом, а циклічна простий ланцюг - простим циклом. Число ребер у маршруті називається його довжиною. Цикл довжини 3 часто називають трикутником. Довжина всякого циклу не менше трьох, якщо мова йде про просте графі, оскільки в такому графі немає петель і кратних ребер. Мінімальна з довжин циклів графа називається його обхватом.
Властивості маршрутів, ланцюгів і циклів:
1) Кожен незамкнений (u, v)-маршрут, містить у собі просту (u, v)-ланцюг. Зокрема, будь-яка (u, v)-ланцюг, містить у собі просту (u, v)-ланцюг. Причому, якщо (u, v)-маршрут містить в собі вершину w (w ≠ u і w ≠ v), то в загальному випадку, проста (u, v)-ланцюг може не містити в собі вершину w.
2) Кожен непростий цикл можна розбити на два або більше простих. Причому для замкнутого маршруту таке твердження не вірно.
3) Будь-яка непроста (u, v)-ланцюг, може бути розбита на просту (u, v)-ланцюг і один або більше простих циклів. Причому для незамкненого маршруту таке твердження не вірно.
4) Для будь-яких трьох вершин u, w, v з існування (u, w)-ланцюга їх і (w, v)-ланцюга, слід існування (u, v)-ланцюга. Причому може не існувати (u, v)-ланцюга, що містить вершину w.
5) Об'єднання двох незбіжних простих (u, v)-ланцюгів містить простий цикл. 6) Якщо граф містить 2 незбіжних циклу із загальним ребром e, то після видалення цього ребра граф як і раніше містить цикл.
Якщо два графа ізоморфні:
1) то вони одного порядку;
2) у них однакова кількість ребер;
3) для довільного i, 0 ≤ i ≤ n-1, (n - порядок графів) кількість вершин ступеня i, в обох графів однаковий;
4) у них збігаються обхвати;
5) у них однакова кількість простих циклів мінімальної довжини (за кількістю ребер).
Граф називається зв'язковим, якщо будь-які дві його неспівпадаючі вершини з'єднані маршрутом. Очевидно, що для зв'язності графа необхідно і достатньо, щоб у ньому для будь-якої фіксованої вершини u і кожної іншої вершини v існував (u, v)-маршрут.
Теорема. Граф G = (V, E) зв'язний тоді і тільки тоді, коли безліч його вершин не можна розбити на два непустих підмножини V1 і V2 так, щоб обидві граничні точки кожного ребра знаходилися в одному і тому ж множині.
Всякий максимальний зв'язний підграф графа G називається зв'язного компонентою (або компонентою) графа G. Слово "максимальний" означає максимальний щодо включення, тобто не міститься в зв'язковому підграфі з великим числом елементів. Безліч вершин зв'язковий компоненти називається областю зв'язності.
Для орієнтованого графа вводиться поняття орієнтованого маршр-та - це послідовність виду (1), в якій ei = (vi, vi +1). Аналогом ланцюга в цій ситуації служити шлях (орієнтована ланцюг). Аналогом циклу служить контур (орієнтований цикл).
Орграф називається сільносвязним, якщо будь-які дві його вершини досяжні одне з одного. Орграф називається одностороннесвязним, якщо для будь-якої пари його вершин принаймні одна досяжна з іншої. Орграф називається сла-босвязним, якщо будь-які дві вершини його заснування з'єднані маршрутом. Орг-раф називається незв'язних, якщо його підставу незв'язний псевдограф.
Теорема. Орграф є сільносвязним тоді і тільки тоді, коли в ньому є остовне циклічний маршрут.
Необхідність. Нехай G - сільносвязний орграф і T = (v0, x1, v1 ,..., xn, v0) - його циклічний маршрут, що проходить через максимально можливе число вершин. Якщо цей маршрут не є кістяк, то візьмемо поза його вершину v. Так як G - сільносвязний орграф, то існують маршрути T1 = (v0, y1, ..., v), T2 = (v, z1, ..., v0). Але тоді циклічний маршрут T '= (v0, x1, v1, ..., xn, v0, y1, ..., v, z1, ..., v0) містить більше число вершин, ніж T, що суперечить вибору маршрутів -та T. Отже, T - остовне маршрут.
Достатність. Нехай u та v - дві довільні вершини орграфа G, а T = (v0, x, ..., v, y, ..., u, z, ..., v0) - циклічний маршрут. Тоді u досяжна з v спомо-могою маршруту (v, y, ..., u) - частини маршруту T, - а v з u - за допомогою маршруту (u, z ,..., v0, x, ... , v) .3
Теорема. Орграф є одностороннесвязним тоді і тільки тоді, коли в ньому є остовне маршрут.
Теорема. Орграф є слабозв'язаних тоді і тільки тоді, коли в його основу є зв'язний псевдограф.
Сільносвязной компонентою орграфа називається його максимальний відноси-тельно включення сільносвязний підграф
МЕТРИЧНІ ХАРАКТЕРИСТИКИ ГРАФА
Нехай G-зв'язний граф, а uі v-дві його неспівпадаючі вершини. Довжина найкоротшого (u, v)-маршруту називається відстанню між вершинами uі vі позначається d (u, v). Покладемо d (u, u) = 0. Очевидно, що введене таким чином відстань задовольняє наступним аксіомам метрики:
1. d (u, v) ≥ 0;
2. d (u, v) = 0 тоді і тільки тоді, коли u = v;
3. d (u, v) = d (v, u);
4. d (u, v) + d (v, w) = d (u, w) (нерівність трикутника).
Для фіксованої вершини u величина e (u) = max d (uv) називається ексцентриситетом вершини u. Максимальний серед усіх ексцентриситетів вершин називається діаметром графа G і позначається через d (G). Тим самим
dG = max e (u)
Вершина v називається периферійною, якщо e (v) = d (G). Проста ланцюг довжини d (G), відстань між кінцями якої дорівнює d (G), називається діаметральної ланцюгом.
Мінімальний з ексцентриситетів вершин зв'язного графа називається його радіусом і позначається через r (G).
Очевидно, що радіус графа не більше його діаметра.

Вершина v називається центральною, якщо e (v) = r (G). Безліч всіх центральних вершин графа називається його центром. Граф може мати єдину центральну вершину або кілька центральних вершин. Нарешті, центр графа може збігатися з безліччю всіх вершин. Наприклад, центр простий ланцюга Pn при парному числі вершин n складається рівно з двох вершин, а при непарному - з однієї; для циклу ж Cn всі вершини є центральними.
Задача знаходження центральних вершин графа постійно виникає у практичній діяльності людей. Нехай, наприклад, граф представляє мережу доріг, тобто вершини його відповідають окремим населеним пунктам, а ребра - дорогами між ними. Потрібно оптимально розмістити лікарні, магазини. У подібних ситуаціях критерій оптимальності часто полягає в оптимізації «найгіршого» випадку, тобто в мінімізації відстані від місця обслуговування до найбільш віддаленого пункту. Отже, місцями розміщення повинні бути центральні вершини графа.
Реальні завдання (їх називають мінімаксних завданнями розміщення) відрізняються від ідеальної тим, що доводиться ще враховувати інші обставини - фактичні відстані між окремими пунктами, вартість, час проїзду та інше. Для того, щоб врахувати це, використовують зважені графи.
ДОДАТОК теорії графів у РІЗНИХ ОБЛАСТЯХ НАУКИ І ТЕХНІКИ.
Інформація.
Двійкові дерева грають дуже важливу роль в теорії інформації. Припустимо, що певна кількість повідомлень потрібно закодувати у вигляді кінцевих послідовностей різної довжини, що складаються з нулів і одиниць. Якщо ймовірності кодових слів задані, то найкращим вважається код, в якому середня довжина слів мінімальна в порівнянні з іншими розподілами ймовірності. Задачу про побудову такого оптимального коду дозволяє вирішити алгоритм Хаффмана.
Двійкові кодові дерева допускають інтерпретацію в рамках теорії пошуку. Кожній вершині при цьому зіставляється питання, відповісти на який можна або "так", або "ні". Стверджувальному і негативної відповіді відповідають два ребра, що виходять з вершини. "Опитування" завершується, коли вдається встановити те, що було потрібно.
Таким чином, якщо комусь знадобиться взяти інтерв'ю у різних людей, і відповідь на чергове запитання буде залежати від заздалегідь невідомого відповіді на попереднє запитання, то план такого інтерв'ю можна представити у вигляді двійкового дерева.
Хімія
Ще А. Келі розглянув задачу про можливі структурах насичених (або граничних) вуглеводнів, молекули яких задаються формулою:
C n H 2n +2
Всі атоми вуглеводню чотиривалентний, всі атоми водню одновалентних. Молекула кожного граничного вуглеводню являє собою дерево. Якщо видалити всі атоми водню, то решта атоми вуглеводню також будуть утворювати дерево, кожна вершина якого має ступінь не вище 4. Отже, число можливих структур граничних вуглеводнів, тобто число гомологів даного речовини, дорівнює числу дерев з вершинами мірою не більше чотирьох.
Таким чином, підрахунок числа гомологів граничних вуглеводнів також приводить до задачі про перерахування дерев певного типу. Це завдання і її узагальнення розглянув Д. Пойа.
Електротехніка.
Ще недавно однією з найбільш складних і утомливих завдань для радіоаматорів було конструювання друкованих схем.
Друкованої схемою називають платівку з якого-небудь діелектрика (ізолюючого матеріалу), на якій у вигляді металевих смужок витравлені доріжки. Перетинатися доріжки можуть тільки в певних точках, куди встановлюються необхідні елементи (діоди, тріоди, резистори й інші), їх перетин в інших місцях викличе замикання електричного кола.
У результаті вирішення цього завдання необхідно викреслити плоский граф, з вершинами у вказаних точках.

ПРАКТИЧНА ЧАСТИНА
a)
SHAPE \ * MERGEFORMAT
x 1
x 2
x 3
x 4
x 5
x 6
u 1
u 2
u 3
u 4
u 5
u 6
u 7
u 8
u 9
u 10
u 11

Матриця суміжності:

Матриця інцидентності:

Матриця відстаней:


Ексцентриситети вершин:
e (x 1) = 2
e (x 2) = 2
e (x 3) = 2
e (x 4) = 2
e (x 5) = 1
e (x 6) = 2
Передавальні числа вершин:
p (x 1) = 6
p (x 2) = 7
p (x 3) = 6
p (x 4) = 7
p (x 5) = 5
p (x 6) = 7
Діаметр графа дорівнює 2, радіус - 1. Центр графа знаходиться у вершині X 5. Медіани графа: x 2, x 4, x 6.
б) SHAPE \ * MERGEFORMAT
x 2
x 1
x 3
x 4
x 5
u 1
u 2
u 3
u 4
u 5
u 6
u 7
u 8


Матриця суміжності:

Матриця інцидентності:

Матриця відстаней:

Ексцентриситети вершин:
e (x 1) = 2
e (x 2) = 2
e (x 3) = 2
e (x 4) = 1
e (x 5) = 2
Передавальні числа вершин:
p (x 1) = 5
p (x 2) = 5
p (x 3) = 5
p (x 4) = 4
p (x 5) = 5
Діаметр графа дорівнює 2, радіус - 1. Центр графа знаходиться у вершині X 4. Медіани графа: x 1, x 2, x 3, x 5.

Лістинг програм
uses crt;
var
A: array [1 .. 100,1 .. 100] of byte;
E, P: array [1 .. 100] of byte;
n, i, j, m, d, r: byte;
begin
clrscr;
writeln ('Enter quantity of tops the column and his matrix of a distance.');
readln (n);
writeln;
for j: = 1 to n do
for i: = 1 to n do
readln (A [i, j]);
clrscr;
for j: = 1 to n do
for i: = 1 to n do
if i = n
then writeln (A [i, j])
else write (A [i, j], '');
writeln;
writeln;
for j: = 1 to n do
begin
m: = A [1, j];
for i: = 1 to n do
begin
if m <A [i, j]
then m: = A [i, j];
end;
E [j]: = m;
end;
for j: = 1 to n do
for i: = 1 to n do
P [j]: = P [j] + A [i, j];
d: = E [1];
for i: = 1 to n do
if d <E [i]
then d: = E [i];
r: = E [1];
for i: = 1 to n do
if r> E [i]
then r: = E [i];
for j: = 1 to n do
writeln ('e (x', j ,')=', E [j]);
writeln;
for j: = 1 to n do
writeln ('p (x', j ,')=', P [j]);
writeln;
writeln ('d (G) =', d);
writeln ('r (G) =', r);
writeln;
writeln ('The centers the column:');
for i: = 1 to n do
if r = E [i]
then write ('x', i, '');
writeln;
writeln ('Medians the column:');
m: = P [1];
for i: = 1 to n do
if m <P [i]
then m: = P [i];
for i: = 1 to n do
if m = P [i]
then write ('x', i, '');
readkey;
end.
Додати в блог або на сайт

Цей текст може містити помилки.

Математика | Курсова
52.4кб. | скачати


Схожі роботи:
Визначення зв`язності графа на Ліспі
Гумор і сатира в поезії графа АК Толстого
Війна і мир головна книга графа ЛН Толстого
Невольник честі про графа Михайла Воронцова
Думка сімейна роман графа ЛН Толстого Анна Кареніна
Оптимізація структури стохастичного графа c змінної інтенсивністю виконання робіт
Характеристики радості
Сигнали та їх характеристики
Лізинги та їх характеристики
© Усі права захищені
написати до нас