Перегляд вихідного коду сторінки Граф (математика)

{{Otheruses|Граф (значення)}}

{{unibox}}[[Файл:Graph.gif|right|frame|Граф із шістьома вершинами та сімома ребрами]]

'''Граф'''&nbsp;— це сукупність об'єктів із зв'язками між ними.

Об'єкти розглядаються як ''вершини'', або ''вузли'' графа, а зв'язки&nbsp;— як ''дуги'', або ''ребра''. Для різних галузей види графів можуть відрізнятися орієнтованістю, обмеженнями на кількість зв'язків і додатковими даними про вершини або ребра.

Ребра графа можуть бути напрямленими або ненапрямленими. Наприклад, якщо вершини будуть представляти людей на вечірці, й існуватиме ребро між двома людьми, якщо вони потиснули руки, тоді ребра цього графа не матимуть напряму, оскільки будь-яка особа ''A'' може потиснути руки із особою ''B'' лише якщо ''B'' також потисне руки із ''A''. На противагу цьому, якщо будь-яке ребро від особи ''A'' до особи ''B'' означатиме, що особі ''A'' подобається ''B'', то ребра матимуть напрям, оскільки таке вподобання не обов'язково буде взаємним. Граф першого типу називається ''неорієнтованим графом'', а ребра в свою чергу&nbsp;— ''неорієнтованими ребрами'', тоді як граф другого типу називається ''орієнтованим графом'' і ребра&nbsp;— ''орієнтованими ребрами'' або ''дугами''.

Велика кількість структур, які мають практичну цінність у [[математика|математиці]] та [[інформатика|інформатиці]], можуть бути подані графами. Наприклад, будову [[Вікіпедія|Вікіпедії]] можна змоделювати за допомогою орієнтованого графа, в якому вершини&nbsp;— це статті, а дуги (орієнтовані ребра)&nbsp;— [[гіпертекст|посилання]] на інші статті.

Граф є основним предметом вивчення в [[Теорія графів|теорії графів]]. Слово «граф» вперше використав в цьому сенсі [[Джеймс Джозеф Сильвестр]] 1878 року.<ref>Див.:
* J. J. Sylvester (February 7, 1878) [https://books.google.com/books?id=KcoKAAAAYAAJ&vq=Sylvester&pg=PA284#v=onepage&q&f=false "Chemistry and algebra, "] {{Webarchive|url=https://web.archive.org/web/20200605015604/https://books.google.com/books?id=KcoKAAAAYAAJ&vq=Sylvester&pg=PA284#v=onepage&q&f=false |date=5 червня 2020 }} ''Nature'', ''17'' : 284. {{doi|10.1038/017284a0}}. From page 284: «Every invariant and covariant thus becomes expressible by a ''graph'' precisely identical with a Kekuléan diagram or chemicograph.»
* J. J. Sylvester (1878) [https://books.google.com/books?id=1q0EAAAAYAAJ&pg=PA64#v=onepage&q&f=false "On an application of the new atomic theory to the graphical representation of the invariants and covariants of binary quantics,&nbsp;— with three appendices, "] {{Webarchive|url=https://web.archive.org/web/20200605002854/https://books.google.com/books?id=1q0EAAAAYAAJ&pg=PA64#v=onepage&q&f=false |date=5 червня 2020 }} ''American Journal of Mathematics, Pure and Applied'', ''1'' (1) : 64–90. {{doi|10.2307/2369436}}. {{JSTOR|2369436}}. The term «graph» first appears in this paper on page 65.</ref><ref>{{Cite book
 | title = Handbook of graph theory
 | first1 = Jonathan L.
 | last1 = Gross
 | first2 = Jay
 | last2 = Yellen
 | publisher = [[CRC Press]]
 | year = 2004
 | page = [https://books.google.com/books?id=mKkIGIea_BkC&pg=PA35&lpg=PA35 35]
 | isbn = 978-1-58488-090-5
 | url = https://books.google.com/?id=mKkIGIea_BkC
 | postscript = <!--None-->}}</ref>

== Історія ==

Першою працею з теорії графів як математичної дисципліни вважають статтю [[Леонард Ейлер|Леонарда Ейлера]] ([[1736]]), у якій розглядалася задача про [[Сім мостів Кеніґсберґа|кенігсберзькі мости]]. Наступний імпульс теорія графів отримала близько 100 років потому з розвитком досліджень електричних мереж, [[кристалографія|кристалографії]], [[органічна хімія|органічної хімії]] та інших наук<ref>{{ref-ru}} ''Белоусов А. И., Ткачев С. Б.'' Дискретная математика: Учебник для вузов / Под ред. В.&nbsp;С.&nbsp;Зарубина, А.&nbsp;П.&nbsp;Крищенко.&nbsp;— 3-е изд., стереотипное.&nbsp;— М.: Издательство МГТУ им. Н.&nbsp;Э.&nbsp;Баумана, 2004. ISBN 5-7038-1270-4.</ref>.

== Визначення ==
{{Main|Словник термінів теорії графів}}

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

=== Граф ===
  {{multiple image
   | right
   | footer    = 
   | width1    = 125
   | image1    = Directed.svg
   | caption1  = Орієнтований граф з трьома вершинами і трьома ребрами.
   | width2    = 125
   | image2    = Undirected.svg
   | caption2  = Простий не орієнтований граф. Кожна вершина має [[Словник_термінів_теорії_графів#С|степінь]] два, тому це буде [[регулярний граф]].
  }}
'''Граф''' або '''неорієнтований граф''' <math>G</math>&nbsp;— це [[впорядкована пара]] <math>G := (V, E)</math>, для якої виконуються такі умови:
:* <math>V</math>&nbsp;— [[множина]] '''вершин''' або '''вузлів''',
:* <math>E</math>&nbsp;— множина пар (у випадку неорієнтованого графа&nbsp;— невпорядкованих) вершин з <math>V</math>, які називаються '''ребрами'''.

<math>V</math> (і так само <math>E</math>) зазвичай вважають [[Скінченна множина|скінченними множинами]]. Багато результатів, отриманих для скінченних графів, неправильні (або інші) для ''нескінченних графів''. Це пов'язано з тим, що певний набір ідей стає хибним у випадку нескінченних множин.

'''Граф (геометричний граф)'''&nbsp;— це [[Геометрична фігура|фігура]] на [[площина|площині]], яка складається з [[Порожня множина|непорожньої]] скінченної [[множина|множини]] ''V'' [[точка|точок]] (вершин) і скінченної множини ''E'' орієнтованих чи не орієнтованих [[лінія|ліній]] (ребер), що з'єднують деякі [[пара|пари]] вершин.

Вершини <math>v_1</math> та <math>v_2</math> називаються ''[[Словник термінів теорії графів#С|суміжними]]'', якщо вони з'єднані ребром <math>e</math>. В такому разі кажуть, що вершини <math>v_1</math> та <math>v_2</math> ''[[Словник термінів теорії графів#І|інцидентні]]'' ребру <math>e</math>, також ребро <math>e</math> інцидентне вершинам <math>v_1</math> та <math>v_2</math>.

Ребра <math>e_1</math> та <math>e_2</math> називаються ''суміжними'', якщо вони ''інцидентні'' вершині <math>v</math>.

=== Орієнтований граф ===
{{Main|Орієнтований граф}}

Граф, який містить тільки ребра називається ''неорієнтованим'', який містить тільки дуги&nbsp;— ''орієнтованим''. Граф, що має як ребра так і дуги, називається ''мішаним''.

Іноді є потреба пару вершин з'єднати більше, ніж одним ребром. Ребра чи дуги одного напряму, які з'єднують ту саму пару вершин, називаються ''[[Кратні ребра|кратними]]'' (паралельними) ребрами.

Дуга чи ребро, що сполучає вершину саму зі собою називається ''петлею''.

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

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

Кожен граф можна відобразити в [[евклідів простір|евклідовому просторі]] множиною [[точка|точок]], які відповідають вершинам, сполучених [[лінія]]ми, що відповідають ребрам (дугам).

[[Мультиграф]]ом називається пара <math>G := (V, E)</math>, де ''<math>V</math>''&nbsp;— множина, елементи якої називаються вершинами. ''<math>E</math>''&nbsp;— сім'я ребер, кожне з яких&nbsp;— це пара вершин із ''<math>V</math>''.

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

{| align="center" class="standard"
|+
!|Тип графа
!|Ребра
!|Кратні ребра
|-----
 | Простий граф
 | Неорієнтовані
 | Ні
|-----
 | Мультиграф
 | Неорієнтовані
 | Так
|-----
 | Орієнтований граф
 | Орієнтовані
 | Ні
|-----
| Орієнтований мультиграф
 | Орієнтовані
 | Так
|+
|}

=== Поняття ===
* '''[[Цикл (теорія графів)|Цикл]]'''&nbsp;— замкнутий ланцюг, для орієнтованих графів цикл називається ''контуром''.
* '''Цикл в орієнтованому графі'''&nbsp;— це простий шлях довжини не менше 1, котрий починається і закінчується в одній і тій самій вершині.
* '''[[Дерево (теорія графів)|Дерево]]'''&nbsp;— зв'язний граф без циклів.

== Способи подання графа в пам'яті комп'ютера ==

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

Надалі вважатимемо, що вершини графа мають номери від '''1''' до '''N''', а ребра&nbsp;— від '''1''' до '''M'''. Кожному ребру і кожній вершині зіставлена вага&nbsp;— ціле додатне число.

=== Матриця суміжності ===
{{Main|Матриця суміжності}}

Матриця суміжності це двовимірний масив розміром '''N*N''':

<syntaxhighlight lang="pascal">
 // матриця суміжності

    Type TAdjacencyMatrix = array [1..N, 1..N] of Integer;
    Var Graph: TAdjacencyMatrix;
</syntaxhighlight>

При цьому '''Graph[i, j]''' дорівнює 0, якщо вершини '''i''' та '''j''' не є суміжними, та '''1''' для суміжних вершин. Для [[Словник термінів теорії графів#З|зваженого графа]] '''Graph[i, j]''' дорівнює вазі вершини '''i''', якщо '''i=j''', а для суміжних вершин&nbsp;— вазі ребра (дуги) з вершини '''i''' у вершину '''j'''.

Просторова складність цього способу '''O(N<sup>2</sup>)'''

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

=== Матриця інцидентності ===
: ''Детальніше [[Матриця інцидентності]]''

Матриця інцидентності це двовимірний масив розміром '''N*M''':

<syntaxhighlight lang="pascal">
// матриця інцидентності

 Type TIncidenceMatrix = array [1..N, 1..M] of Integer;
 Var Graph: TIncidenceMatrix;
</syntaxhighlight>

При цьому '''Graph[i, j]''' дорівнює 0, якщо вершини '''i''' та ребро '''j''' не є інцидентними, −1, якщо вершина '''i''' є кінцем орієнтованого ребра '''j''', +1, якщо вершина '''i''' є початком орієнтованого ребра '''j'''. Інколи зручно користуватись означенням, у якому '''Graph[i, j]''' дорівнює вазі ребра (дуги) '''j''', що є інцидентним вершині '''i'''.

Матриця інцидентності найкраще підходить для операції перерахування ребер, що є інцидентними вершині '''x'''.

=== Списки суміжності ===
: ''Детальніше [[Список суміжності]]''

Список суміжності це послідовність (масив, список) розміром '''N''', кожен елемент якої є списком вершин суміжних з даною:

<syntaxhighlight lang="pascal">
// список суміжності

 Type TAdjacencyList = array [1..N] of record
   Count: Integer; {кількість елементів у списку}
   List: array[1..N] of 
       record {список}
        Node, {номер суміжної вершини}
        Weight: Integer; {вага ребра}
       end;
   end;
   Var Graph: AdjacencyList; 
</syntaxhighlight>

Цей спосіб збереження найкраще підходить для перерахування усіх вершин суміжних з '''x'''.

=== Список ребер ===
: ''Детальніше [[Список ребер]]''

<syntaxhighlight lang="pascal">
 // динамічний список ребер (із вказівниками)

 // застосовують тоді, коли кількість ребер невідома наперед і їх багато

   Type ListElPtr=^ListEl;   {вершини графа позначені числами }
                                             {(номерами)}
     ListE l= record
     Node1, Node2: integer; {список складаються із пар цілих чисел: }
                                 {перше - звідки ребро, друге - куди}
     Next:ListElPtr;              {вказівник на наступне ребро графа}
   end;
 // список (масив) ребер

 // застосовують тоді, коли кількість ребер відома наперед і невелика


   Type TBranchList = array [1..M] of 
      record
       Node1, Node2, {пари вершин, що зв'язує ребро}
       Weight: Integer; {вага ребра}
   end;
   Var Graph: BranchList;
</syntaxhighlight>

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

== Застосування графів ==
[[Файл:Граф-збагачення.svg|right|thumb|350px|Застосування графа в моделюванні (описі) процесів [[збагачення корисних копалин]]]]

Графи використовуються в різних галузях науки і техніки, зокрема:
* [[Файлова система]] комп'ютера. Ієрархія файлів та тек в багатьох [[операційна система|операційних системах]] має вигляд дерева, яке є окремим випадком графа;
* [[Молекула|Молекули]] всіх хімічних речовин можна зобразити у вигляді графа, де атоми є вершинами, а зв'язки між ними&nbsp;— ребрами;
* Карта автомобільних чи будь-яких інших шляхів також є графом, причому кожна дорога може мати певне значення «ваги» (наприклад, щільність транспортного потоку), тоді такий граф є зваженим;
* [[Соціальна мережа|Соціальну мережу]] також можна подати у вигляді графа, де кожна людина чи [[соціальна група]] є вершиною, а зв'язки між ними&nbsp;— ребрами;
* [[Генеалогія|Генеалогічне дерево]] є прикладом [[Двійкове дерево|бінарного дерева]], яке є окремим випадком графа;
* Турнірну таблицю спортивного чемпіонату також можна зобразити у вигляді графа;
* В [[біологія|біології]] та [[екологія|екології]] також використовуються графи. Прикладами є [[харчовий ланцюжок|ланцюги харчування]], [[екосистема|екосистеми]], генетичні послідовності та карти, [[таксон]]омічна ієрархія живих організмів тощо;
* В [[археологія|археології]] та [[геологія|геології]] графи використовуються у [[стратиграфія|стратиграфії]] для вивчення геологічних пластів;
* Будь-який виробничий процес також можна зобразити у вигляді графа (див. приклад&nbsp;— технологічна схема [[збагачення корисних копалин]]);
* Розробка програмного забезпечення та комп'ютерні науки взагалі є однією з тих галузей, де графи застосовуються найчастіше. Складність та велика кількість [[модульне програмування|модулів]] і [[комунікаційний протокол|протоколів]] у сучасних програмних продуктах дуже ускладнює розуміння їх роботи, керування нею та її оптимізацію, тому дуже часто складаються графи програм, причому найчастіше це робиться автоматично [[транслятор]]ами чи [[компілятор]]ами. Графи також є зручними для зображення структур даних, [[блок-схема|блок-схем]], [[потік даних|потоків даних]], схем [[база даних|баз даних]] та [[база знань|баз знань]], [[скінченний автомат|скінченних автоматів]], схем [[мережа комп'ютерна|комп'ютерних мереж]] та окремих [[сайт]]ів, [[граф викликів|схем викликів]] [[підпрограма|підпрограм]] тощо. Також графи широко використовуються в багатьох [[Алгоритм пошуку|алгоритмах пошуку]] та [[Алгоритм сортування|сортування]]. Крім того, одним з головних напрямків сучасних досліджень у царині глобальних мереж є задане консорціумом [[W3C]] завдання побудови [[семантична мережа|семантичної мережі]] (один з видів графів) на базі мережі [[Інтернет]].

== Див. також ==
{{Портал|Математика}}
* [[Операції над графами]]
* [[Дерево (теорія графів)]]
* [[Цикломатичне число]]
* [[Маршрут (теорія графів)]]
* [[Матриця суміжності]]
* [[Словник термінів теорії графів]]
* [[Граф хімічних реакцій]]
* [[Хімічна теорія графів]]
* [[Мережа]]
* [[Центр графа]]
* [[Циклічний ранг]]
* [[Ранг (теорія графів)]]

== Література ==
* {{книга
|автор        = Спекторський І. Я.
|заголовок    = Дискретна математика
|рік          = 
|видавництво  = Політехніка
|місто        = {{Comment|К.|Київ}}
|сторінок     = 220
|ISBN = 966-622-136-5
}}
* {{cite book |назва             = Graph Theory with Applications
 |автор             = [http://www.ecp6.jussieu.fr/pageperso/bondy/bondy.html J.A. Bondy], U.S.R. Murty
 |дата               = 1976
 |видавництво = [http://www.elsevier.com Elsevier/North-Holland]
 |url                    = https://archive.org/details/graphtheorywitha0000bond/page/264
 |сторінки       = [https://archive.org/details/graphtheorywitha0000bond/page/264 264 c.]
 |isbn                   = 0-444-19451-7
 |accessdate             = 27 квітня 2008
 |deadurl                = yes
}} {{ref-en}}
* {{cite book
 |назва             = Graph Theory
 |автор             = J.A. Bondy, U.S.R. Murty
 |дата               = 2008
 |видавництво = [http://www.springer.com/ Springer]
 |url                    = http://www.springer.com/math/numbers/book/978-1-84628-969-9
 |сторінки       = 654 c.
 |isbn                   = 978-1-84628-969-9
 |accessdate             = 27 квітня 2008
 |archive-date           = 11 травня 2008
 |archive-url            = https://web.archive.org/web/20080511024556/http://www.springer.com/math/numbers/book/978-1-84628-969-9
}} {{ref-en}}
* {{cite book
 |назва             = Graphs, Networks and Algorithms
 |автор             = Jungnickel, Dieter
 |дата               = 2008
 |видавництво = [http://www.springer.com/ Springer]
 |url                    = http://www.springer.com/math/numbers/book/978-3-540-72779-8
 |сторінки       = 650 c.
 |isbn                   = 978-3-540-72779-8
 |accessdate             = 30 квітня 2008
 |archive-date           = 13 червня 2008
 |archive-url            = https://web.archive.org/web/20080613090104/http://www.springer.com/math/numbers/book/978-3-540-72779-8
}} {{ref-en}}
* {{cite book|
назва=C++ Boost Graph Library |
автор = Сик Дж., Ли Л., Ламсдэйн Э. | 
дата=2006| 
видавництво= [http://www.piter.com/ Питер] | 
сторінки=  304 c.|
isbn = 978-5-469-00352-6 }} {{ref-en}}
* {{cite book|
назва=Algorithms in Java, Third Edition, Part 5: Graph Algorithms | url=https://archive.org/details/algorithmsinjava0000sedg |
автор = Robert Sedgewick | 
дата=2003| 
видавництво= Addison Wesley | 
сторінки=  528 c.|
isbn = 0-201-36121-3 }} {{ref-en}}
* {{книга
|автор        = Березина Л. Ю.
|заголовок    = Графы и их применение
|рік          = 2009
|видавництво  = URSS
|місто        = {{Comment|М.|Москва}}
|сторінок     = 152
}}{{ref-ru}}
* {{книга
|автор        = Берж К.
|заголовок    = Теория графов и ее применения
|рік          = 1962
|видавництво  = ИЛ
|місто        = {{Comment|М.|Москва}}
|сторінок     = 320
}}{{ref-ru}}
* {{книга
|автор        = Голиков А. П., [[Черваньов Ігор Григорович|Черванёв И. Г.]], Трофимов А. М.
|заголовок    = Математические методы в географии
|рік          = 1986
|видавництво  = Изд-во ХГУ
|місто        = {{Comment|Х.|Харків}}
|сторінок     = 143
}}{{ref-ru}}
* {{книга
|автор        = Ловас Л., Пламмер М.
|заголовок    = Прикладные задачи теории графов
|рік          = 1998
|видавництво  = Мир
|місто        = {{Comment|М.|Москва}}
|сторінок     = 656
}}{{ref-ru}}
* {{книга
|автор        = Михеева В. С.
|заголовок    = Математические методы в экономической географии
|частина      = Приложение теории графов: Курс лекций (ч. 2)
|рік          = 1983
|видавництво  = Изд-во МГУ
|місто        = {{Comment|М.|Москва}}
}}{{ref-ru}}
* {{книга
|автор        = Оре О.
|заголовок    = Теория графов
|рік          = 1980
|видавництво  = Наука
|місто        = {{Comment|М.|Москва}}
|сторінок     = 336
}}{{ref-ru}}
* {{книга
|автор        = Татт У.
|заголовок    = Теория графов
|рік          = 1988
|видавництво  = Мир
|місто        = {{Comment|М.|Москва}}
|сторінок     = 424
}}{{ref-ru}}
* {{книга
|автор        = Фляйшнер Г.
|заголовок    = Эйлеровы графы и смежные вопросы
|рік          = 2002
|видавництво  = Мир
|місто        = {{Comment|М.|Москва}}
|сторінок     = 176
}}{{ref-ru}}
* {{книга
|автор        = Харари Ф.
|заголовок    = Теория графов
|рік          = 1973
|видавництво  = Мир
|місто        = {{Comment|М.|Москва}}
|сторінок     = 304
}}{{ref-ru}}

== Примітки ==
{{reflist}}

{{math-stub}}{{без виносок|дата=серпень 2020}}
[[Категорія:Теорія графів]]
[[Категорія:Об'єкти теорії графів]]
[[Категорія:Статті з прикладами коду мовою Pascal]]