Azərbaycanca AzərbaycancaБеларускі БеларускіDansk DanskDeutsch DeutschEspañola EspañolaFrançais FrançaisIndonesia IndonesiaItaliana Italiana日本語 日本語Қазақ ҚазақLietuvos LietuvosNederlands NederlandsPortuguês PortuguêsРусский Русскийසිංහල සිංහලแบบไทย แบบไทยTürkçe TürkçeУкраїнська Українська中國人 中國人United State United StateAfrikaans Afrikaans
Підтримка
www.wikidata.uk-ua.nina.az

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

Компонента зв'язності графа

Компонента зв'язності графа

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

image
Граф з трьома компонентами зв'язності

Відношення еквівалентності

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

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

  • рефлексивність: Існує тривіальний шлях нульової довжини від вершини до самої себе.
  • симетричність: Якщо існує шлях від u до v, тоді ті самі ребра утворюють шлях від v до u.
  • транзитивність: Якщо існує шлях від u до v і шлях від v до w, обидва шляхи можуть бути об'єднані в шлях від u до w.

Тоді компоненти зв'язності це підграфи утворені класами еквівалентності цього відношення.

Див. також

Посилання

  • Connected components [ 23 Лютого 2011 у Wayback Machine.], Steven Skiena, The Stony Brook Algorithm Repository
image Це незавершена стаття про алгоритми.
Ви можете проєкту, виправивши або дописавши її.

Вікіпедія, Українська, Україна, книга, книги, бібліотека, стаття, читати, завантажити, безкоштовно, безкоштовно завантажити, mp3, відео, mp4, 3gp, jpg, jpeg, gif, png, малюнок, музика, пісня, фільм, книга, гра, ігри, мобільний, телефон, android, ios, apple, мобільний телефон, samsung, iphone, xiomi, xiaomi, redmi, honor, oppo, nokia, sonya, mi, ПК, web, Інтернет

V teoriyi grafiv komponenta zv yaznosti neoriyentovanogo grafa ce v yakomu bud yaki dvi vershini zv yazani odna z odnoyu shlyahami i voni ne zv yazani z niyakimi dodatkovimi vershinami Napriklad graf na malyunku pravoruch maye tri komponenti zv yaznosti Zv yaznij graf maye rivno odnu komponentu zv yaznosti yaka mistit ves graf Graf z troma komponentami zv yaznostiVidnoshennya ekvivalentnostiShe odnim shlyahom viznachennya komponent zv yaznosti zaluchaye klasi ekvivalentnosti vershin grafa V neoriyentovanomu grafi vershina v dosyazhna z vershini u yaksho isnuye shlyah z u do v V comu viznachenni okrema vershina prijmayetsya yak shlyah nulovoyi dovzhini i odna i ta sama vershina mozhe zustrichatis bilsh nizh raz uzdovzh shlyahu Dosyazhnist ce vidnoshennya ekvivalentnosti bo vikonuyutsya pravila refleksivnist Isnuye trivialnij shlyah nulovoyi dovzhini vid vershini do samoyi sebe simetrichnist Yaksho isnuye shlyah vid u do v todi ti sami rebra utvoryuyut shlyah vid v do u tranzitivnist Yaksho isnuye shlyah vid u do v i shlyah vid v do w obidva shlyahi mozhut buti ob yednani v shlyah vid u do w Todi komponenti zv yaznosti ce pidgrafi utvoreni klasami ekvivalentnosti cogo vidnoshennya Div takozhFaktor grafPosilannyaConnected components 23 Lyutogo 2011 u Wayback Machine Steven Skiena The Stony Brook Algorithm Repository Ce nezavershena stattya pro algoritmi Vi mozhete dopomogti proyektu vipravivshi abo dopisavshi yiyi

Дата публікації:
Топ