Графи та їх застосування

 

Міністерство освіти і науки, молоді та спорту України

Сумський державний  педагогічний університет імені  А.С. Макаренка

 

 

Кафедра математики

 

Мандій  Яна Анатоліївна

 

 

ДИПЛОМНА  РОБОТА

ГРАФИ ТА ЇХ ЗАСТОСУВАННЯ

 

Напрям  підготовки 0402 Фізико-математичні науки

Спеціальність 7.04020101 Математика*

Освітньо-кваліфікаційний  рівень «Спеціаліст»

 

 

 

 

 

Науковий керівник – 

доктор фізико-математичних

наук, професор

Лиман Федір  Миколайович

 

 

 

 

Суми – 2012

 

Зміст

ВСТУП 4

РОЗДІЛ 1. ЗАГАЛЬНІ ВІДОМОСТІ ПРО ТЕОРІЮ ГРАФІВ 8

1.1. Що таке граф? 8

1.1.1. Задача про кенігсберзькі мости 9

1.1.2. Основні поняття теорії графів 12

1.2. Основні  способи задання графів 19

1.2.1. Задання  графа за допомогою матриці  інцидентності та списку ребер 19

1.2.2. Задання  графа за допомогою матриці  суміжності 22

1.3. Ізоморфізм  графів 24

1.4. Планарність  графів 28

1.4.1. Застосування  теореми Ейлера до деяких завдань 31

1.4.2. Критерії  планарності 34

1.5. Одна задача  про плоскі графи 38

1.6. Ейлерові  графи 41

1.7. Маршрути  та зв′язність у графах 46

1.8. Дерева  та ліси 53

РОЗДІЛ 2. ОРІЄНТОВАНІ  ГРАФИ ТА РОЗФАРБУВАННЯ ГРАФІВ 57

2.1. Орієнтовані  графи 57

2.1.1. Модель  орграфа 57

2.1.2. Маршрути  в орграфах 60

2.1.3. Турніри 63

2.2. Розфарбування  графів 65

2.2.1. Хроматичне  число графа 65

2.2.2.  Гіпотеза  чотирьох фарб та теорема про  п’ять фарб для 67

планарних графів 67

РОЗДІЛ 3. ЗАСТОСУВАННЯ ТЕОРІЇ ГРАФІВ В ОКРЕМИХ ГАЛУЗЯХ  НАУКИ 71

3.1. Фізика 71

3.2. Хімія 77

3. 3. Біологія  і психологія 80

3.4. Інформатика 81

3.4.1. Програмування 82

3.4.2. Графи  як об’єкти обробки інформації 83

3.5. Математика 88

РОЗДІЛ 4. ГРАФИ  В ШКІЛЬНОМУ КУРСІ МАТЕМАТИКИ 97

4.1. Аналіз  навчальних програм з теми  дослідження 97

4.1.1. Програма  спеціального курсу «Прикладна  математика для учнів 8-11 класів  з поглибленим вивченням математики» 97

4.1.2. факультативна  програма з математики «Економіка  в задачах математики» 98

4.1.3. Програма  розвитку творчого мислення  учнів  (Шахи, інтелектуальні ігри. Основи  математичної логіки. Інтегрований  курс навчання.) 98

4.2. Факультативне  заняття з теорії графів для  учнів  11  класу на тему: «Граф.  Розв’язування задач за допомогою  графа» 99

ВИСНОВКИ 106

СПИСОК ВИКОРИСТАНИХ ДЖЕРЕЛ 108

ДОДАТКИ 111

 

 

ВСТУП

 

Спробуйте намалювати «заклеяний конверт» одним розчерком пера, тобто  не відриваючи ручки від паперу й  не проводячи двічі один і той  самий відрізок. Такого роду запитання  з давніх-давен  цікавили математиків.

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

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

В наш час теорія графів є дуже актуальною. Вона використовується у багатьох сферах людського життя  для опису взаємозв’яків між  об’єктами, процесами чи подіями. Граф – це  досить чітка модель для  вивчення окремих явищ навколишньої дійсності. Тому темою нашої дипломної  роботи є „Графи та їх застосування”, адже теорія графів має не тільки наукову, а й практичну цінність. Останнім часом зв’язані з графами методи досліджень використовуються не тільки в математиці, але і у фізиці, хімії, біології, інформатиці, географії  та інших науках.

Отже, практична цінність теорії графів безперечна.

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

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

Об’єктом  дослідження  є теорія графів.

Предметом  дослідження в даній дипломній роботі виступає теорія графів, властивості графів, основні способи їх задання, основні теореми теорії графів та сфера їх застосування.

Методи: теоретичний аналіз навчальної і науково-методичної літератури з даної теми.

Завдання:

1. Аналіз навчальної, науково-методичної та періодичної  літератури з теми дослідження;
2. Дослідження основних означень та теорем теорії графів.
3. З᾿ясування області застосування теорії графів.

Під час виконання роботи нами було проведено аналіз періодичної  літератури, такої як науково-популярний фізико-математичний журнал «Квант», міжнародний  збірник «Дидактика математики: проблеми і дослідження», науково-теоретичний  і методичний журнал «Математика  в школі», де було знайдено багато цікавих  статей з даної теми, які ми використовували  під час виконання роботи.

Перша робота з теорії графів, яка належить відомому швейцарському  математику Л.Ейлера, з’явилась в 1736р. Спочатку теорія графів здавалась досить незначним розділом математики, так  як вона мала справу з математичними  розвагами та головоломками. Однак  подальший розвиток математики і  особливо її розділів дало сильний  поштовх розвитку теорії графів. Уже  в XIX ст. графи використовувалися  при побудові схем електричних ланцюгів і молекулярних схем. В дійсний  час можна вказати і розділи чистої математики, наприклад теорія математичних відношень, в яких теорія графів слугує природнім апаратом; з іншої сторони, при вирішенні транспортних задач, задач про потоки в мережі нафтопроводів і взагалі в так званому «програмуванні». Теорія графів тепер застосовується і в таких областях, як економіка, психологія і біологія. Математичні розваги і головоломки також залишаються частиною теорії графів, особливо якщо віднести до них знамениту проблему «чотирьох фарб», яка цікавить математиків до цього часу.

В математиці  теорія графів розглядається як одна із віток топології; безпосереднє відношення має також  до алгебри і до теорії графів.

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

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

Дослідженням теорії графів займалися багато науковців сучасності, серед них: кандидат фізико-математичних наук, професор Р.М. Трохимчук, доктор фізико-математичних наук, професор Сущанський В.І., кандидат фізико-математичних наук,  доцент  Шевченко В.П., кандидат фізико-математичних наук Зиков А. А., кандидат фізико-математичних наук Берж К., кандидат фізико-математичних наук Оре О. та інші.

 

 

 

РОЗДІЛ 1. ЗАГАЛЬНІ ВІДОМОСТІ ПРО ТЕОРІЮ ГРАФІВ

 

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

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

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

 

1. Що таке граф?

 

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

Граф – це множина точок (вершин), які з′єднані між собою лініями, що називаються дугами або ребрами.

 Приведемо приклад  задачі, яка може бути розв′язана, за допомогою графів.

Задача 1.1.

 На вечірку запрошено  шестеро людей, чи може бути  така ситуація,

 що кожен знав тільки  двох запрошених.

 Розв′язання:

 Кожного з цієї компанії  зобразимо точкою  і пронумеруємо  їх. Якщо двоє знайомі, то з′єднаємо  їх відрізком (ребром). Виявляється,  що така ситуація не тільки можлива, але й може описуватися декількома схемами (див. рис.1.1.).

                                                  Рис.1.1.          

  

 Тобто можна сказати,  що граф - це сукупність об′єктів,  зв′язками між якими служать  ребра.

На рис. 2 показаний граф з чотирма вершинами та шістьма  ребрами, а 

 на рис. 3 зображено  граф з п′ятьма вершинами та  двома ребрами.

Рис.2

 

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

1. Задача про кенігсберзькі мости

 

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

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

Батьком теорії графів (так  само як і топології) є Ейлер (1707-1782рр.), який в 1736 році розв’язав досить відому в ті часи задачу, яка називалась «проблемою кенігсберзьких мостів». В  місті Кенігсберг було два острови, з’єднаних сімома містками з берегами річки Преголя і один з одним  таким чином, як показано на рис. 1.1. [28, c.13-14].

Рис. 1.1.

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

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

Для доведення того, що дана задача не має розв’язку, Ейлер позначив кожну частину суходолу точкою (вершиною), а кожен міст – лінією (ребром), яка з’єднує відповідні точки. Отримали «граф».  Цей граф показаний на рис.1.2, де точки  позначені тими ж буквами, що і частини суходолу на рис.1.1.

Рис. 1.2.

Твердження про неіснування  стверджувального розв’язку у цій  задачі еквівалентне твердженню  про  неможливість обійти спеціальним чином  граф, представлений на рис.1.2.

Відштовхуючись від цього  частинного випадку, Ейлер узагальнив постановку задачі і знайшов критерій існування обходу (спеціального маршруту) у даному графі, а саме граф повинен  бути зв’язним і кожна його вершина  повинна бути інцидентною парній кількості ребер. Граф, показаний  на рис.1.2, зв’язний, але не кожна  його вершина інцидентна парній кількості ребер [29, c. 16].

Ейлер підрахував число ребер, що виходить з кожної вершини графа (рис.1.2.). З вершин В, С і Д виходить по три ребра, а з вершини А – п’ять ребер. Вершини графа, з яких виходить непарна кількість ребер, він назвав непарними вершинами, а вершини, з яких виходить парна кількість ребер, - парними. Всі вершини даного графа виявились непарними.

В ході розв’язання цієї задачі Ейлер встановив наступні чотири властивості зв’язного графа:

1. Кількість непарних  вершин графа завжди парна.  Неможливо зобразити граф, який  мав би непарне число непарних  вершин.

2. Якщо всі вершини  графа парні, то можна одним  розчерком (тобто без відриву  олівця від паперу проводячи  по кожному ребрі тільки один  раз) зобразити граф, при цьому  рух можна починати з будь-якої  вершини і закінчити в тій  самій вершині.

3. граф тільки з двома  непарними вершинами можна зобразити  одним розчерком, при цьому  рух можна починати з однієї  з цих непарних вершин і  закінчити в іншій.

4. Граф з більш ніж  з двома непарними вершинами  неможливо зобразити одним розчерком [36, c. 21-22].

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

2. Основні поняття теорії графів

 

Вище було розглянуто інтуїтивно описане поняття графа. Формалізуємо його.

Нехай V – не порожня множина, V(2) – множина всіх його двоелементних підмножин. Пара (V, E), де E – довільна підмножина множини V(2), називається графом (неорієнтованим графом).

Елементи множини V називаються вершинами. Елементи множини E – ребрами. Отже, граф – довільна множина вершин V і довільний набір E пар вершин, або ребер, причому E ≤ V(2). Множини ребер і вершин графа G позначають символами EG та VG відповідно. Вершини і ребра графа називають його елементами. Число вершин графа G називається його порядком і позначається через | VG | або просто | G |, число ребер позначається | EG |. Якщо | VG |= n, | EG | = m, то G називається (n, m) – графом [33, c.27].

Невпорядкована пара вершин називається ребром, впорядкована – дугою графа.

Граф, який містить тільки ребра називається неорієнтованим. Граф, який містить лише дуги – орієнтованим графом.

Пара вершин може з’єднуватись двома або більше ребрами (дугами одного напрямку), такі ребра (дуги) називаються кратними.

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

Іноді під графом розуміють  граф, без петель і кратних ребер, тоді граф, в якому допускаються кратні ребра, називається мультографом, а граф, в якому допускаються кратні ребра і петлі називається псевдо графом.

Вершини, з’єднані ребром або  дугою, називаються суміжними. Ребра, які мають спільну вершину, теж називають суміжними. Ребро (дуга) і будь-яка з його двох вершин називаються інцидент ними. Говорять, що ребро (u, v) з’єднує вершини u і v, а дуга (u, v) починається в вершині u і закінчується в вершині v.

 Множина всіх вершин  графа G, суміжних з деякою вершиною v, називається оточенням вершини v і позначається або NG(v)  або N(v).

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

В ролі ілюстрації розглянемо граф G, зображений на рис. 1.3.

Рис.1.3.

Це (6,7) – граф, VG = {1,2,3,4,5,6}, EG = {{1,2}, {2,3}, {3,6}, {3,5}, {2,6}, {2,5}, {2,4}, {6,4}}. Вершини 1, 2 – суміжні, а 1, 3 – не суміжні. Вершина 4 і ребро {2,4} – інцидентні. N(2) = {1,2,3,4,5,6}, N(5) = {2,3,6} – оточення вершин 2 і 5 [20, c.43].

Граф G називається повним, якщо будь-які дві вершини графа суміжні.

Повний граф порядку n позначається символом Kn, число ребер в ньому рівне α. На рис.1.4. зображені графи Kn для n ≤ 5.

Рис. 1.4.

Граф називається порожнім, якщо в ньому немає ребер. Порожній граф порядку n позначається через Оn (рис.1.5, а).

Цикл –це замкнений ланцюг. Ланцюг – лінія на графі, що не проходить ні по якому ребрі графа більше одного разу.

На рис.1.5,б показані прості цикли Сn (n=3,4), на рис.1.5.(в) – прості ланцюги Рn (n = 2,3,4).

Рис.1.5.

Очевидно, що К2 = Р2, а К3 = С3. На рис.1.6. показано два зображення простого циклу С5.

Рис.1.6.

На рис.1.7. зображено колеса Wn (n = 3,4,5).

Зазначимо, що W3  = K4 і |W| = n + 1.

Рис.1.7.

На рис.1.8. зображений граф Петерсена.

Рис.1.8.

Далі в роботі неодноразово будуть використовуватись поняття  «розбиття» та «покриття».

Набір підмножини S називається покриттям множини S, якщо об’єднання цих підмножин співпадає з S.

Покриття називають розбиттям, якщо ніякі дві підмножини, що входять в нього, не перетинаються [8, c.56-57].

Граф називається дводольним, якщо існує таке розбиття множин його вершин на дві частини (долі), що кінці кожного ребра належать різним частинам. Якщо при цьому будь-які дві вершини, які входять в різні долі, суміжні, то граф називається повним дводольним. Повний дводольний граф , долі якого складаються із p і q вершин, позначається символом К_р,q.

При р=1 отримуємо зірку К_1,q.

Очевидно, що К_1,1 =К₂=Р₂, К_1,2=Р₃, К_2,2=С₄. Зазначимо, що одна з долей дводольного графа може бути пустою.

Так О₁ – дводольний граф з однією пустою долею, О₂ можна трактувати як дводольний граф з двома одновершинними долями, або як дводольний граф, одна з долей якого містить дві вершини, а друга є пустою множиною.

На рис.1.9. зображено зірку К_1,6, повний дводольний граф К_3,3, дводольний граф К_2,3.

                  K_1,6                                    K_3,3                                     K_2,3

Рис.1.9.

Аналогічно дводольним визначають k-дольний і повний  k-дольний графи для k=3,4,… .На рис.1.10 зображено трьохдольний граф.

Рис.1.10

Два графа G(V,E) i H(W,I) називаються ізоморфними, якщо існує взаємно-однозначна відповідність між множинами V,W і множинами ребер E,I, яка зберігає відношення інцидентності [6, c.28].

Наприклад, три графи зображені  на рис. 1.11. ізоморфні, а графи, зображені  на рис.1.12. – не ізоморфні.

Рис.1.11.

 

Рис.1.12

Іноді наведене вище поняття  графа є недостатнім і доволиться розглядати більш загальні об’єкти, в яких дві вершини можуть з’єднуватись більш ніж одним ребром. Так  виникає поняття «мультограф». Мультограф – це пара (V,E), де V – непорожня множина (вершин), а E – сімейство підмножини множини Е (ребер). Використання терміну «сімейство» замість множини означає, що елементи множини Е можуть повторюватись, тобто допускаються кратні ребра.

Подальше узагальнення полягає  в тому, що окрім кратних ребер  допускаються ще петлі, тобто ребра, що з’єднують вершину саму з собою. Псевдограф – це пара  (V,E), де V – не порожня множина (вершин), а E – деяке сімейство невпорядкованих пар  вершин (ребер), не обов’язково різних. На рис. 1.13.(а) зображено мультограф, а на рис.1.13.(б) – псевдо граф.

Рис.1.13.

Визначаються також і  орієнтовані графи. Орієнтований граф (орграф) – це пара (V,A), де V – множина вершин, А – множина орієнтованих ребер, які називаються дугами. Якщо а=(v₁, v₂) – дуга, то вершини v₁ і v₂ називаються її початком і кінцем відповідно. На рисунку дуги помічаються стрілками, що вказують напрям від початку до кінця (рис.1.14(а)). Аналогічно визначається орієнтований мультограф (рис.1.14(б)).

Рис.1.14.

Розглядаються також графи, у яких є дуги, і неорієнтовані  ребра.

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

1.2. Основні способи  задання графів

 

Існує декілька способів задання  графів.

Одним зі способів задання  графа G =(V,E ) є задання кожної з множин V і E за допомогою переліку їх елементів.

Приклад 1. Граф G₁=(V₁, E₁), V₁={v₁,v₂,v₃,v₄} і E₁={(v₁,v₃), (v₁,v₄),(v₂,v₃),(v₂,v₄),(v₃,v₄)} - це граф із чотирма вершинами і п’ятьма ребрами.

А граф G₂=(V₂,E₂), V₂={v₁,v₂,v₃,v₄,v₅} і E₂={(v₁,v₂),(v₂,v₄),(v₁,v₅), (v₃,v₂),(v₃,v₅),(v₄,v₁),(v₅,v₄)} - граф із п’ятьма вершинами і сімома ребрами.

Граф G =(V,E ) зручно зображати за допомогою рисунка на площині, який називають діаграмою графа G. Вершинам графа G ставляться у бієктивну відповідність точки площини; точки, що відповідають вершинам v i w, з’єднуються лінією (відрізком або кривою) тоді і тільки тоді, коли v i w суміжні вершини. Зрозуміло, що діаграма графа змінюватиме свій вигляд у залежності від вибору відповідних точок на площині.

Приклад 2. На рис.1.15. зображені діаграми графів G₁ i G₂ з попереднього прикладу.

Рис. 1.15.

Графи можна задавати також  за допомогою матриць.

 

1.2.1. Задання графа  за допомогою матриці інцидентності  та списку ребер

 

Задати граф означає задати для нього множину вершин і  ребер, а також відношення інцидентності. Коли граф G – скінчений, для опису його вершин і ребер достатньо їх занумерувати. Нехай v1, v2, …, vn – вершини графа G;            е1, е2, … , еn – його ребра. Відношення інцидентностві можна означити матрицею | E | = || ε_ij ||,  що має m рядків і n стовпців. Стовпці відповідають вершинам графа, а рядки – його ребрам. Якщо ребро еі є інцидентним вершині v_j,  то ε_ij = 0. Це – матриця інцидентності графа G, яка є одним із способів його визначення для графа, заданого на рис.1.15 [36, c.180-182].

У матриці інцидентності || ε_ij || орієнтованого графа G, якщо v_j – початок ребра е_i, то ε_ij = -1; якщо v_j – кінець е_i, то ε_ij = 1; якщо е_i – петля, а v_j – інцидентна їй вершина, то ε_ij = α, де α – будь-яке число, відмінне від 0, 1 та -1, в інших випадках ε_ij = 0.

Матриця інцидентності  для графа, зображеного на рис.1.16 .             Таблиця 1

	v1	v2	v3	v4	v5	v6	v7
e1	1	1	0	0	0	0	0
e2	1	0	1	0	0	0	0
e3	0	1	0	1	0	0	0
e4	1	0	0	0	1	0	0
e5	0	1	0	0	0	1	0
e6	0	0	1	1	0	0	0
e7	0	0	1	0	1	0	0
e8	0	0	0	1	0	1	0
e9	0	0	0	0	1	0	1
e10	0	0	0	0	0	1	1
e11	0	0	0	0	1	1	0