Azərbaycanca
Беларускі
Dansk
Deutsch
Española
Français
Indonesia
Italiana
日本語
Қазақ
Lietuvos
Nederlands
Português
Русский
සිංහල
แบบไทย
Türkçe
Українська
中國人
United State
Afrikaans
| Ця стаття не містить . (липень 2013) |
Зв'язний граф — граф, що містить рівно одну компоненту зв'язності. Це значить, що між будь-якою парою вершин цього графа існує шлях.
Приклади використання
Прямим використанням теорії графів є теорія мереж — та її застосування — теорія електронних мереж. Наприклад, всі комп'ютери, що знаходяться в мережі інтернет, утворюють зв'язний граф, і хоча окрема пара комп'ютерів може бути не з'єднана безпосередньо (в формулюванні для графів — не бути поєднаною ребром), від кожного комп'ютера можна передати інформацію до будь-якого іншого (існує шлях з будь-якої вершини графа до будь-якої іншої).
Кількість зв'язних графів
Кількість зв'язних графів з розміткою вершин наведено в Енциклопедії послідовностей цілих чисел як послідовність A001187 [ 20 січня 2022 у Wayback Machine.]:
| n | Кількість |
|---|---|
| 1 | 1 |
| 2 | 1 |
| 3 | 4 |
| 4 | 38 |
| 5 | 728 |
| 6 | 26704 |
| 7 | 1866256 |
| 8 | 251548592 |
Зв'язність для орієнтованих графів
В орієнтованих графах розрізняють декілька понять зв'язності.
Орієнтований граф називається сильно-зв'язним, якщо в ньому існує (орієнтований) шлях з будь-якої вершини до будь-якої іншої, або, що тотожно, граф містить рівно одну компоненту сильної зв'язності.
Орієнтований граф називається односторонньо-зв'язним, якщо для будь-яких двох його вершин u і v існує хоча б один з маршрутів від v до u чи від u до v.
Орієнтований граф називається слабко-зв'язним, якщо є зв'язним неорієнтований граф, отриманий з нього заміною орієнтованих ребер на неорієнтовані.
Деякі критерії зв'язності
Тут наведені деякі критеріальні (тотожні) визначення зв'язного графа:
Граф називається однозв'язним (зв'язним), якщо:
- У нього одна компонента зв'язності
- Між будь-якою парою вершин існує шлях, що поєднує їх
- Існує шлях із заданої вершини в будь-яку іншу
- Граф містить зв'язний підграф, що містить всі вершини початкового графа
- Містить як підграф дерево, що містить всі вершини початкового графа (таке дерево називається кістяковим)
- За довільним поділом його вершин на дві групи завжди існує хоча б одне ребро, що поєднує пару вершин з різних груп
Див. також
Вікіпедія, Українська, Україна, книга, книги, бібліотека, стаття, читати, завантажити, безкоштовно, безкоштовно завантажити, mp3, відео, mp4, 3gp, jpg, jpeg, gif, png, малюнок, музика, пісня, фільм, книга, гра, ігри, мобільний, телефон, android, ios, apple, мобільний телефон, samsung, iphone, xiomi, xiaomi, redmi, honor, oppo, nokia, sonya, mi, ПК, web, Інтернет
Cya stattya ne mistit posilan na dzherela Vi mozhete dopomogti polipshiti cyu stattyu dodavshi posilannya na nadijni avtoritetni dzherela Material bez dzherel mozhe buti piddano sumnivu ta vilucheno lipen 2013 Zv yaznij graf graf sho mistit rivno odnu komponentu zv yaznosti Ce znachit sho mizh bud yakoyu paroyu vershin cogo grafa isnuye shlyah Cej graf perestane buti zv yaznim yaksho viluchiti rebro poznachene punktirnoyu liniyeyu Prikladi vikoristannyaPryamim vikoristannyam teoriyi grafiv ye teoriya merezh ta yiyi zastosuvannya teoriya elektronnih merezh Napriklad vsi komp yuteri sho znahodyatsya v merezhi internet utvoryuyut zv yaznij graf i hocha okrema para komp yuteriv mozhe buti ne z yednana bezposeredno v formulyuvanni dlya grafiv ne buti poyednanoyu rebrom vid kozhnogo komp yutera mozhna peredati informaciyu do bud yakogo inshogo isnuye shlyah z bud yakoyi vershini grafa do bud yakoyi inshoyi Kilkist zv yaznih grafivKilkist i zobrazhennya zv yazanih grafiv z 4 vershinami Kilkist zv yaznih grafiv z rozmitkoyu vershin navedeno v Enciklopediyi poslidovnostej cilih chisel yak poslidovnist A001187 20 sichnya 2022 u Wayback Machine n Kilkist1 12 13 44 385 7286 267047 18662568 251548592Zv yaznist dlya oriyentovanih grafivV oriyentovanih grafah rozriznyayut dekilka ponyat zv yaznosti Oriyentovanij graf nazivayetsya silno zv yaznim yaksho v nomu isnuye oriyentovanij shlyah z bud yakoyi vershini do bud yakoyi inshoyi abo sho totozhno graf mistit rivno odnu komponentu silnoyi zv yaznosti Oriyentovanij graf nazivayetsya odnostoronno zv yaznim yaksho dlya bud yakih dvoh jogo vershin u i v isnuye hocha b odin z marshrutiv vid v do u chi vid u do v Oriyentovanij graf nazivayetsya slabko zv yaznim yaksho ye zv yaznim neoriyentovanij graf otrimanij z nogo zaminoyu oriyentovanih reber na neoriyentovani Deyaki kriteriyi zv yaznostiTut navedeni deyaki kriterialni totozhni viznachennya zv yaznogo grafa Graf nazivayetsya odnozv yaznim zv yaznim yaksho U nogo odna komponenta zv yaznosti Mizh bud yakoyu paroyu vershin isnuye shlyah sho poyednuye yih Isnuye shlyah iz zadanoyi vershini v bud yaku inshu Graf mistit zv yaznij pidgraf sho mistit vsi vershini pochatkovogo grafa Mistit yak pidgraf derevo sho mistit vsi vershini pochatkovogo grafa take derevo nazivayetsya kistyakovim Za dovilnim podilom jogo vershin na dvi grupi zavzhdi isnuye hocha b odne rebro sho poyednuye paru vershin z riznih grupDiv takozhTeorema Mengera Perevirka zv yaznosti grafiv Ciklichnij rang Zhorstkist grafa