Граф — це сукупність об'єктів із зв'язками між ними.
Граф | |
Досліджується в | теорія графів |
---|---|
Формула | |
Позначення у формулі | , , і |
Підтримується Вікіпроєктом | |
Граф у Вікісховищі |
Об'єкти розглядаються як вершини, або вузли графу, а зв'язки — як дуги, або ребра. Для різних галузей види графів можуть відрізнятися орієнтованістю, обмеженнями на кількість зв'язків і додатковими даними про вершини або ребра.
Ребра графу можуть бути напрямленими або ненапрямленими. Наприклад, якщо вершини будуть представляти людей на вечірці, й існуватиме ребро між двома людьми, якщо вони потиснули руки, тоді ребра цього графу не матимуть напряму, оскільки будь-яка особа A може потиснути руки із особою B лише якщо B також потисне руки із A. На противагу цьому, якщо будь-яке ребро від особи A до особи B означатиме, що особі A подобається B, то ребра матимуть напрям, оскільки таке вподобання не обов'язково буде взаємним. Граф першого типу називається неорієнтованим графом, а ребра в свою чергу — неорієнтованими ребрами, тоді як граф другого типу називається орієнтованим графом і ребра — орієнтованими ребрами або дугами.
Велика кількість структур, які мають практичну цінність у математиці та інформатиці, можуть бути подані графами. Наприклад, будову Вікіпедії можна змоделювати за допомогою орієнтованого графу, в якому вершини — це статті, а дуги (орієнтовані ребра) — посилання на інші статті.
Граф є основним предметом вивчення в теорії графів. Слово «граф» вперше використав в цьому сенсі Джеймс Джозеф Сильвестр 1878 року.
Історія
Першою працею з теорії графів як математичної дисципліни вважають статтю Леонарда Ейлера (1736), у якій розглядалася задача про кенігсберзькі мости. Наступний імпульс теорія графів отримала близько 100 років потому з розвитком досліджень електричних мереж, кристалографії, органічної хімії та інших наук.
Визначення
Теорія графів не має стійкої термінології. В різних статтях під одними й тими ж термінами розуміють різні поняття. Наведені нижче визначення належать до найбільш розповсюджених.
Граф
Граф або неорієнтований граф — це впорядкована пара , для якої виконуються такі умови:
- — множина вершин або вузлів,
- — множина пар (у випадку неорієнтованого графу — невпорядкованих) вершин з , які називаються ребрами.
(і так само ) зазвичай вважають скінченними множинами. Багато результатів, отриманих для скінченних графів, неправильні (або інші) для нескінченних графів. Це пов'язано з тим, що певний набір ідей стає хибним у випадку нескінченних множин.
Граф (геометричний граф) — це фігура на площині, яка складається з непорожньої скінченної множини V точок (вершин) і скінченної множини E орієнтованих чи не орієнтованих ліній (ребер), що з'єднують деякі пари вершин.
Вершини та називаються (суміжними), якщо вони з'єднані ребром . В такому разі кажуть, що вершини та (інцидентні) ребру , також ребро інцидентне вершинам та .
Ребра та називаються суміжними, якщо вони інцидентні вершині .
Орієнтований граф
Граф, який містить тільки ребра називається неорієнтованим, який містить тільки дуги — орієнтованим. Граф, що має як ребра так і дуги, називається мішаним.
Іноді є потреба пару вершин з'єднати більше, ніж одним ребром. Ребра чи дуги одного напряму, які з'єднують ту саму пару вершин, називаються кратними (паралельними) ребрами.
Дуга чи ребро, що сполучає вершину саму зі собою називається петлею.
Граф без кратних дуг і петель називається простим.
Вершини сполучені ребром чи дугою називаються суміжними, також називаються суміжними ребра, що мають спільну вершину. Ребро (чи дуга) і її вершина називаються інцидентними. Ребро (u, v) з'єднує вершини u і v, дуга (u, v) починається у вершині u і закінчується у вершині v.
Кожен граф можна відобразити в евклідовому просторі множиною точок, які відповідають вершинам, сполучених лініями, що відповідають ребрам (дугам).
Мультиграфом називається пара , де — множина, елементи якої називаються вершинами. — сім'я ребер, кожне з яких — це пара вершин із .
Мультиграф, який може мати петлі, іноді називають псевдографом.
Тип графу | Ребра | Кратні ребра |
---|---|---|
Простий граф | Неорієнтовані | Ні |
Мультиграф | Неорієнтовані | Так |
Орієнтований граф | Орієнтовані | Ні |
Орієнтований мультиграф | Орієнтовані | Так |
Поняття
Способи подання графу в пам'яті комп'ютера
Якщо мережу автомобільних доріг, ліній комунікацій чи будь-який граф взагалі треба використати в комп'ютерній програмі, то постає проблема збереження інформації про цей граф у пам'яті комп'ютера. Вибір структури даних для збереження графу в пам'яті є визначальним у процесі розробки ефективних алгоритмів.
Надалі вважатимемо, що вершини графу мають номери від 1 до N, а ребра — від 1 до M. Кожному ребру і кожній вершині зіставлена вага — ціле додатне число.
Матриця суміжності
Матриця суміжності це двовимірний масив розміром N*N:
// матриця суміжності Type TAdjacencyMatrix = array [1..N, 1..N] of Integer; Var Graph: TAdjacencyMatrix;
При цьому Graph[i, j] дорівнює 0, якщо вершини i та j не є суміжними, та 1 для суміжних вершин. Для (зваженого графу) Graph[i, j] дорівнює вазі вершини i, якщо i=j, а для суміжних вершин — вазі ребра (дуги) з вершини i у вершину j.
Просторова складність цього способу O(N2)
Цей спосіб застосовують тоді, коли в задачі треба часто перевіряти суміжність чи знаходити вагу ребра за двома заданими вершинами.
Матриця інцидентності
- Детальніше Матриця інцидентності
Матриця інцидентності це двовимірний масив розміром N*M:
// матриця інцидентності Type TIncidenceMatrix = array [1..N, 1..M] of Integer; Var Graph: TIncidenceMatrix;
При цьому Graph[i, j] дорівнює 0, якщо вершини i та ребро j не є інцидентними, −1, якщо вершина i є кінцем орієнтованого ребра j, +1, якщо вершина i є початком орієнтованого ребра j. Інколи зручно користуватись означенням, у якому Graph[i, j] дорівнює вазі ребра (дуги) j, що є інцидентним вершині i.
Матриця інцидентності найкраще підходить для операції перерахування ребер, що є інцидентними вершині x.
Списки суміжності
- Детальніше
Список суміжності це послідовність (масив, список) розміром N, кожен елемент якої є списком вершин суміжних з даною:
// список суміжності Type TAdjacencyList = array [1..N] of record Count: Integer; {кількість елементів у списку} List: array[1..N] of record {список} Node, {номер суміжної вершини} Weight: Integer; {вага ребра} end; end; Var Graph: AdjacencyList;
Цей спосіб збереження найкраще підходить для перерахування усіх вершин суміжних з x.
Список ребер
- Детальніше
// динамічний список ребер (із вказівниками) // застосовують тоді, коли кількість ребер невідома наперед і їх багато 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;
Цей спосіб збереження графу є особливо зручним, якщо головною операцією є перерахування ребер або пошук вершин і ребер, що знаходяться у відносинах інцидентності.
Застосування графів
Графи використовуються в різних галузях науки і техніки, зокрема:
- Файлова система комп'ютера. Ієрархія файлів та тек в багатьох операційних системах має вигляд дерева, яке є окремим випадком графу;
- Молекули всіх хімічних речовин можна зобразити у вигляді графу, де атоми є вершинами, а зв'язки між ними — ребрами;
- Карта автомобільних чи будь-яких інших шляхів також є графом, причому кожна дорога може мати певне значення «ваги» (наприклад, щільність транспортного потоку), тоді такий граф є зваженим;
- Соціальну мережу також можна подати у вигляді графу, де кожна людина чи соціальна група є вершиною, а зв'язки між ними — ребрами;
- Генеалогічне дерево є прикладом бінарного дерева, яке є окремим випадком графу;
- Турнірну таблицю спортивного чемпіонату також можна зобразити у вигляді графу;
- В біології та екології також використовуються графи. Прикладами є ланцюги харчування, екосистеми, генетичні послідовності та карти, таксономічна ієрархія живих організмів тощо;
- В археології та геології графи використовуються у стратиграфії для вивчення геологічних пластів;
- Будь-який виробничий процес також можна зобразити у вигляді графу (див. приклад — технологічна схема збагачення корисних копалин);
- Розробка програмного забезпечення та комп'ютерні науки взагалі є однією з тих галузей, де графи застосовуються найчастіше. Складність та велика кількість модулів і протоколів у сучасних програмних продуктах дуже ускладнює розуміння їх роботи, керування нею та її оптимізацію, тому дуже часто складаються графи програм, причому найчастіше це робиться автоматично трансляторами чи компіляторами. Графи також є зручними для зображення структур даних, блок-схем, потоків даних, схем баз даних та баз знань, скінченних автоматів, схем комп'ютерних мереж та окремих сайтів, підпрограм тощо. Також графи широко використовуються в багатьох алгоритмах пошуку та сортування. Крім того, одним з головних напрямків сучасних досліджень у царині глобальних мереж є задане консорціумом W3C завдання побудови семантичної мережі (один з видів графів) на базі мережі Інтернет.
Див. також
Література
- Спекторський І. Я. Дискретна математика. — К. : Політехніка. — 220 с. — .
- J.A. Bondy, U.S.R. Murty (1976). Graph Theory with Applications. Elsevier/North-Holland. с. 264 c. ISBN . Процитовано 27 квітня 2008.
{{}}
: Обслуговування CS1: Сторінки з параметром url-status, але без параметра archive-url () (англ.) - J.A. Bondy, U.S.R. Murty (2008). . Springer. с. 654 c. ISBN . Архів оригіналу за 11 травня 2008. Процитовано 27 квітня 2008. (англ.)
- Jungnickel, Dieter (2008). . Springer. с. 650 c. ISBN . Архів оригіналу за 13 червня 2008. Процитовано 30 квітня 2008. (англ.)
- Сик Дж., Ли Л., Ламсдэйн Э. (2006). C++ Boost Graph Library. Питер. с. 304 c. ISBN . (англ.)
- Robert Sedgewick (2003). Algorithms in Java, Third Edition, Part 5: Graph Algorithms. Addison Wesley. с. 528 c. ISBN . (англ.)
- Березина Л. Ю. Графы и их применение. — М. : URSS, 2009. — 152 с.(рос.)
- Берж К. Теория графов и ее применения. — М. : ИЛ, 1962. — 320 с.(рос.)
- Голиков А. П., Черванёв И. Г., Трофимов А. М. Математические методы в географии. — Х. : Изд-во ХГУ, 1986. — 143 с.(рос.)
- Ловас Л., Пламмер М. Прикладные задачи теории графов. — М. : Мир, 1998. — 656 с.(рос.)
- Михеева В. С. Приложение теории графов: Курс лекций (ч. 2) // Математические методы в экономической географии. — М. : Изд-во МГУ, 1983.(рос.)
- Оре О. Теория графов. — М. : Наука, 1980. — 336 с.(рос.)
- Татт У. Теория графов. — М. : Мир, 1988. — 424 с.(рос.)
- Фляйшнер Г. Эйлеровы графы и смежные вопросы. — М. : Мир, 2002. — 176 с.(рос.)
- Харари Ф. Теория графов. — М. : Мир, 1973. — 304 с.(рос.)
Примітки
- Див.:
- J. J. Sylvester (February 7, 1878) "Chemistry and algebra, " [ 5 червня 2020 у Wayback Machine.] 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) "On an application of the new atomic theory to the graphical representation of the invariants and covariants of binary quantics, — with three appendices, " [ 5 червня 2020 у Wayback Machine.] 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.
- Gross, Jonathan L.; Yellen, Jay (2004). Handbook of graph theory. CRC Press. с. 35. ISBN .
- (рос.) Белоусов А. И., Ткачев С. Б. Дискретная математика: Учебник для вузов / Под ред. В. С. Зарубина, А. П. Крищенко. — 3-е изд., стереотипное. — М.: Издательство МГТУ им. Н. Э. Баумана, 2004. .
Це незавершена стаття з математики. Ви можете проєкту, виправивши або дописавши її. |
Ця стаття містить , але походження тверджень у ній через практично повну відсутність . (серпень 2020) |
Вікіпедія, Українська, Україна, книга, книги, бібліотека, стаття, читати, завантажити, безкоштовно, безкоштовно завантажити, mp3, відео, mp4, 3gp, jpg, jpeg, gif, png, малюнок, музика, пісня, фільм, книга, гра, ігри, мобільний, телефон, android, ios, apple, мобільний телефон, samsung, iphone, xiomi, xiaomi, redmi, honor, oppo, nokia, sonya, mi, ПК, web, Інтернет
U Vikipediyi ye statti pro inshi znachennya cogo termina Graf znachennya Graf ce sukupnist ob yektiv iz zv yazkami mizh nimi Graf Doslidzhuyetsya vteoriya grafiv FormulaG V E displaystyle G V E Poznachennya u formuliG displaystyle G V displaystyle V E displaystyle E i displaystyle Pidtrimuyetsya VikiproyektomVikipediya Proyekt Matematika Graf u VikishovishiGraf iz shistoma vershinami ta simoma rebrami Ob yekti rozglyadayutsya yak vershini abo vuzli grafu a zv yazki yak dugi abo rebra Dlya riznih galuzej vidi grafiv mozhut vidriznyatisya oriyentovanistyu obmezhennyami na kilkist zv yazkiv i dodatkovimi danimi pro vershini abo rebra Rebra grafu mozhut buti napryamlenimi abo nenapryamlenimi Napriklad yaksho vershini budut predstavlyati lyudej na vechirci j isnuvatime rebro mizh dvoma lyudmi yaksho voni potisnuli ruki todi rebra cogo grafu ne matimut napryamu oskilki bud yaka osoba A mozhe potisnuti ruki iz osoboyu B lishe yaksho B takozh potisne ruki iz A Na protivagu comu yaksho bud yake rebro vid osobi A do osobi B oznachatime sho osobi A podobayetsya B to rebra matimut napryam oskilki take vpodobannya ne obov yazkovo bude vzayemnim Graf pershogo tipu nazivayetsya neoriyentovanim grafom a rebra v svoyu chergu neoriyentovanimi rebrami todi yak graf drugogo tipu nazivayetsya oriyentovanim grafom i rebra oriyentovanimi rebrami abo dugami Velika kilkist struktur yaki mayut praktichnu cinnist u matematici ta informatici mozhut buti podani grafami Napriklad budovu Vikipediyi mozhna zmodelyuvati za dopomogoyu oriyentovanogo grafu v yakomu vershini ce statti a dugi oriyentovani rebra posilannya na inshi statti Graf ye osnovnim predmetom vivchennya v teoriyi grafiv Slovo graf vpershe vikoristav v comu sensi Dzhejms Dzhozef Silvestr 1878 roku IstoriyaPershoyu praceyu z teoriyi grafiv yak matematichnoyi disciplini vvazhayut stattyu Leonarda Ejlera 1736 u yakij rozglyadalasya zadacha pro kenigsberzki mosti Nastupnij impuls teoriya grafiv otrimala blizko 100 rokiv potomu z rozvitkom doslidzhen elektrichnih merezh kristalografiyi organichnoyi himiyi ta inshih nauk ViznachennyaDokladnishe Slovnik terminiv teoriyi grafiv Teoriya grafiv ne maye stijkoyi terminologiyi V riznih stattyah pid odnimi j timi zh terminami rozumiyut rizni ponyattya Navedeni nizhche viznachennya nalezhat do najbilsh rozpovsyudzhenih Graf Oriyentovanij graf z troma vershinami i troma rebrami Prostij ne oriyentovanij graf Kozhna vershina maye stepin dva tomu ce bude regulyarnij graf Graf abo neoriyentovanij graf G displaystyle G ce vporyadkovana para G V E displaystyle G V E dlya yakoyi vikonuyutsya taki umovi V displaystyle V mnozhina vershin abo vuzliv E displaystyle E mnozhina par u vipadku neoriyentovanogo grafu nevporyadkovanih vershin z V displaystyle V yaki nazivayutsya rebrami V displaystyle V i tak samo E displaystyle E zazvichaj vvazhayut skinchennimi mnozhinami Bagato rezultativ otrimanih dlya skinchennih grafiv nepravilni abo inshi dlya neskinchennih grafiv Ce pov yazano z tim sho pevnij nabir idej staye hibnim u vipadku neskinchennih mnozhin Graf geometrichnij graf ce figura na ploshini yaka skladayetsya z neporozhnoyi skinchennoyi mnozhini V tochok vershin i skinchennoyi mnozhini E oriyentovanih chi ne oriyentovanih linij reber sho z yednuyut deyaki pari vershin Vershini v 1 displaystyle v 1 ta v 2 displaystyle v 2 nazivayutsya sumizhnimi yaksho voni z yednani rebrom e displaystyle e V takomu razi kazhut sho vershini v 1 displaystyle v 1 ta v 2 displaystyle v 2 incidentni rebru e displaystyle e takozh rebro e displaystyle e incidentne vershinam v 1 displaystyle v 1 ta v 2 displaystyle v 2 Rebra e 1 displaystyle e 1 ta e 2 displaystyle e 2 nazivayutsya sumizhnimi yaksho voni incidentni vershini v displaystyle v Oriyentovanij graf Dokladnishe Oriyentovanij graf Graf yakij mistit tilki rebra nazivayetsya neoriyentovanim yakij mistit tilki dugi oriyentovanim Graf sho maye yak rebra tak i dugi nazivayetsya mishanim Inodi ye potreba paru vershin z yednati bilshe nizh odnim rebrom Rebra chi dugi odnogo napryamu yaki z yednuyut tu samu paru vershin nazivayutsya kratnimi paralelnimi rebrami Duga chi rebro sho spoluchaye vershinu samu zi soboyu nazivayetsya petleyu Graf bez kratnih dug i petel nazivayetsya prostim Vershini spolucheni rebrom chi dugoyu nazivayutsya sumizhnimi takozh nazivayutsya sumizhnimi rebra sho mayut spilnu vershinu Rebro chi duga i yiyi vershina nazivayutsya incidentnimi Rebro u v z yednuye vershini u i v duga u v pochinayetsya u vershini u i zakinchuyetsya u vershini v Kozhen graf mozhna vidobraziti v evklidovomu prostori mnozhinoyu tochok yaki vidpovidayut vershinam spoluchenih liniyami sho vidpovidayut rebram dugam Multigrafom nazivayetsya para G V E displaystyle G V E de V displaystyle V mnozhina elementi yakoyi nazivayutsya vershinami E displaystyle E sim ya reber kozhne z yakih ce para vershin iz V displaystyle V Multigraf yakij mozhe mati petli inodi nazivayut psevdografom Tip grafu Rebra Kratni rebra Prostij graf Neoriyentovani Ni Multigraf Neoriyentovani Tak Oriyentovanij graf Oriyentovani Ni Oriyentovanij multigraf Oriyentovani Tak Ponyattya Cikl zamknutij lancyug dlya oriyentovanih grafiv cikl nazivayetsya konturom Cikl v oriyentovanomu grafi ce prostij shlyah dovzhini ne menshe 1 kotrij pochinayetsya i zakinchuyetsya v odnij i tij samij vershini Derevo zv yaznij graf bez cikliv Sposobi podannya grafu v pam yati komp yuteraYaksho merezhu avtomobilnih dorig linij komunikacij chi bud yakij graf vzagali treba vikoristati v komp yuternij programi to postaye problema zberezhennya informaciyi pro cej graf u pam yati komp yutera Vibir strukturi danih dlya zberezhennya grafu v pam yati ye viznachalnim u procesi rozrobki efektivnih algoritmiv Nadali vvazhatimemo sho vershini grafu mayut nomeri vid 1 do N a rebra vid 1 do M Kozhnomu rebru i kozhnij vershini zistavlena vaga cile dodatne chislo Matricya sumizhnosti Dokladnishe Matricya sumizhnosti Matricya sumizhnosti ce dvovimirnij masiv rozmirom N N matricya sumizhnosti Type TAdjacencyMatrix array 1 N 1 N of Integer Var Graph TAdjacencyMatrix Pri comu Graph i j dorivnyuye 0 yaksho vershini i ta j ne ye sumizhnimi ta 1 dlya sumizhnih vershin Dlya zvazhenogo grafu Graph i j dorivnyuye vazi vershini i yaksho i j a dlya sumizhnih vershin vazi rebra dugi z vershini i u vershinu j Prostorova skladnist cogo sposobu O N2 Cej sposib zastosovuyut todi koli v zadachi treba chasto pereviryati sumizhnist chi znahoditi vagu rebra za dvoma zadanimi vershinami Matricya incidentnosti Detalnishe Matricya incidentnosti Matricya incidentnosti ce dvovimirnij masiv rozmirom N M matricya incidentnosti Type TIncidenceMatrix array 1 N 1 M of Integer Var Graph TIncidenceMatrix Pri comu Graph i j dorivnyuye 0 yaksho vershini i ta rebro j ne ye incidentnimi 1 yaksho vershina i ye kincem oriyentovanogo rebra j 1 yaksho vershina i ye pochatkom oriyentovanogo rebra j Inkoli zruchno koristuvatis oznachennyam u yakomu Graph i j dorivnyuye vazi rebra dugi j sho ye incidentnim vershini i Matricya incidentnosti najkrashe pidhodit dlya operaciyi pererahuvannya reber sho ye incidentnimi vershini x Spiski sumizhnosti Detalnishe Spisok sumizhnosti ce poslidovnist masiv spisok rozmirom N kozhen element yakoyi ye spiskom vershin sumizhnih z danoyu spisok sumizhnosti Type TAdjacencyList array 1 N of record Count Integer kilkist elementiv u spisku List array 1 N of record spisok Node nomer sumizhnoyi vershini Weight Integer vaga rebra end end Var Graph AdjacencyList Cej sposib zberezhennya najkrashe pidhodit dlya pererahuvannya usih vershin sumizhnih z x Spisok reber Detalnishe dinamichnij spisok reber iz vkazivnikami zastosovuyut todi koli kilkist reber nevidoma napered i yih bagato Type ListElPtr ListEl vershini grafa poznacheni chislami nomerami ListE l record Node1 Node2 integer spisok skladayutsya iz par cilih chisel pershe zvidki rebro druge kudi Next ListElPtr vkazivnik na nastupne rebro grafa end spisok masiv reber zastosovuyut todi koli kilkist reber vidoma napered i nevelika Type TBranchList array 1 M of record Node1 Node2 pari vershin sho zv yazuye rebro Weight Integer vaga rebra end Var Graph BranchList Cej sposib zberezhennya grafu ye osoblivo zruchnim yaksho golovnoyu operaciyeyu ye pererahuvannya reber abo poshuk vershin i reber sho znahodyatsya u vidnosinah incidentnosti Zastosuvannya grafivZastosuvannya grafu v modelyuvanni opisi procesiv zbagachennya korisnih kopalin Grafi vikoristovuyutsya v riznih galuzyah nauki i tehniki zokrema Fajlova sistema komp yutera Iyerarhiya fajliv ta tek v bagatoh operacijnih sistemah maye viglyad dereva yake ye okremim vipadkom grafu Molekuli vsih himichnih rechovin mozhna zobraziti u viglyadi grafu de atomi ye vershinami a zv yazki mizh nimi rebrami Karta avtomobilnih chi bud yakih inshih shlyahiv takozh ye grafom prichomu kozhna doroga mozhe mati pevne znachennya vagi napriklad shilnist transportnogo potoku todi takij graf ye zvazhenim Socialnu merezhu takozh mozhna podati u viglyadi grafu de kozhna lyudina chi socialna grupa ye vershinoyu a zv yazki mizh nimi rebrami Genealogichne derevo ye prikladom binarnogo dereva yake ye okremim vipadkom grafu Turnirnu tablicyu sportivnogo chempionatu takozh mozhna zobraziti u viglyadi grafu V biologiyi ta ekologiyi takozh vikoristovuyutsya grafi Prikladami ye lancyugi harchuvannya ekosistemi genetichni poslidovnosti ta karti taksonomichna iyerarhiya zhivih organizmiv tosho V arheologiyi ta geologiyi grafi vikoristovuyutsya u stratigrafiyi dlya vivchennya geologichnih plastiv Bud yakij virobnichij proces takozh mozhna zobraziti u viglyadi grafu div priklad tehnologichna shema zbagachennya korisnih kopalin Rozrobka programnogo zabezpechennya ta komp yuterni nauki vzagali ye odniyeyu z tih galuzej de grafi zastosovuyutsya najchastishe Skladnist ta velika kilkist moduliv i protokoliv u suchasnih programnih produktah duzhe uskladnyuye rozuminnya yih roboti keruvannya neyu ta yiyi optimizaciyu tomu duzhe chasto skladayutsya grafi program prichomu najchastishe ce robitsya avtomatichno translyatorami chi kompilyatorami Grafi takozh ye zruchnimi dlya zobrazhennya struktur danih blok shem potokiv danih shem baz danih ta baz znan skinchennih avtomativ shem komp yuternih merezh ta okremih sajtiv pidprogram tosho Takozh grafi shiroko vikoristovuyutsya v bagatoh algoritmah poshuku ta sortuvannya Krim togo odnim z golovnih napryamkiv suchasnih doslidzhen u carini globalnih merezh ye zadane konsorciumom W3C zavdannya pobudovi semantichnoyi merezhi odin z vidiv grafiv na bazi merezhi Internet Div takozhPortal Matematika Operaciyi nad grafami Derevo teoriya grafiv Ciklomatichne chislo Marshrut teoriya grafiv Matricya sumizhnosti Slovnik terminiv teoriyi grafiv Graf himichnih reakcij Himichna teoriya grafiv Merezha Centr grafa Ciklichnij rang Rang teoriya grafiv LiteraturaSpektorskij I Ya Diskretna matematika K Politehnika 220 s ISBN 966 622 136 5 J A Bondy U S R Murty 1976 Graph Theory with Applications Elsevier North Holland s 264 c ISBN 0 444 19451 7 Procitovano 27 kvitnya 2008 a href wiki D0 A8 D0 B0 D0 B1 D0 BB D0 BE D0 BD Cite book title Shablon Cite book cite book a Obslugovuvannya CS1 Storinki z parametrom url status ale bez parametra archive url posilannya angl J A Bondy U S R Murty 2008 Springer s 654 c ISBN 978 1 84628 969 9 Arhiv originalu za 11 travnya 2008 Procitovano 27 kvitnya 2008 angl Jungnickel Dieter 2008 Springer s 650 c ISBN 978 3 540 72779 8 Arhiv originalu za 13 chervnya 2008 Procitovano 30 kvitnya 2008 angl Sik Dzh Li L Lamsdejn E 2006 C Boost Graph Library Piter s 304 c ISBN 978 5 469 00352 6 angl Robert Sedgewick 2003 Algorithms in Java Third Edition Part 5 Graph Algorithms Addison Wesley s 528 c ISBN 0 201 36121 3 angl Berezina L Yu Grafy i ih primenenie M URSS 2009 152 s ros Berzh K Teoriya grafov i ee primeneniya M IL 1962 320 s ros Golikov A P Chervanyov I G Trofimov A M Matematicheskie metody v geografii H Izd vo HGU 1986 143 s ros Lovas L Plammer M Prikladnye zadachi teorii grafov M Mir 1998 656 s ros Miheeva V S Prilozhenie teorii grafov Kurs lekcij ch 2 Matematicheskie metody v ekonomicheskoj geografii M Izd vo MGU 1983 ros Ore O Teoriya grafov M Nauka 1980 336 s ros Tatt U Teoriya grafov M Mir 1988 424 s ros Flyajshner G Ejlerovy grafy i smezhnye voprosy M Mir 2002 176 s ros Harari F Teoriya grafov M Mir 1973 304 s ros PrimitkiDiv J J Sylvester February 7 1878 Chemistry and algebra 5 chervnya 2020 u Wayback Machine Nature 17 284 DOI 10 1038 017284a0 From page 284 Every invariant and covariant thus becomes expressible by a graph precisely identical with a Kekulean diagram or chemicograph J J Sylvester 1878 On an application of the new atomic theory to the graphical representation of the invariants and covariants of binary quantics with three appendices 5 chervnya 2020 u Wayback Machine 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 Gross Jonathan L Yellen Jay 2004 Handbook of graph theory CRC Press s 35 ISBN 978 1 58488 090 5 ros Belousov A I Tkachev S B Diskretnaya matematika Uchebnik dlya vuzov Pod red V S Zarubina A P Krishenko 3 e izd stereotipnoe M Izdatelstvo MGTU im N E Baumana 2004 ISBN 5 7038 1270 4 Ce nezavershena stattya z matematiki Vi mozhete dopomogti proyektu vipravivshi abo dopisavshi yiyi Cya stattya mistit perelik posilan ale pohodzhennya tverdzhen u nij zalishayetsya nezrozumilim cherez praktichno povnu vidsutnist vnutrishnotekstovih dzherel vinosok Bud laska dopomozhit polipshiti cyu stattyu peretvorivshi dzherela z pereliku posilan na dzherela vinoski u samomu teksti statti serpen 2020