Зв'язний граф

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

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

Приклади використання

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

Кількість зв'язних графів

Кількість і зображення зв'язаних графів з 4 вершинами

Кількість зв'язних графів з розміткою вершин наведено в Енциклопедії послідовностей цілих чисел як послідовність 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.

Орієнтований граф називається слабко-зв'язним, якщо є зв'язним неорієнтований граф, отриманий з нього заміною орієнтованих ребер на неорієнтовані.

Деякі критерії зв'язності

Тут наведені деякі критеріальні (тотожні) визначення зв'язного графа:

Граф називається однозв'язним (зв'язним), якщо:

  1. У нього одна компонента зв'язності
  2. Між будь-якою парою вершин існує шлях, що поєднує їх
  3. Існує шлях із заданої вершини в будь-яку іншу
  4. Граф містить зв'язний підграф, що містить всі вершини початкового графа
  5. Містить як підграф дерево, що містить всі вершини початкового графа (таке дерево називається кістяковим)
  6. За довільним поділом його вершин на дві групи завжди існує хоча б одне ребро, що поєднує пару вершин з різних груп

Див. також

Read other articles:

Kimia teoretis

Bagian dari seriIlmu Pengetahuan Formal Logika Matematika Logika matematika Statistika matematika Ilmu komputer teoretis Teori permainan Teori keputusan Ilmu aktuaria Teori informasi Teori sistem FisikalFisika Fisika klasik Fisika modern Fisika terapan Fisika komputasi Fisika atom Fisika nuklir Fisika partikel Fisika eksperimental Fisika teori Fisika benda terkondensasi Mekanika Mekanika klasik Mekanika kuantum Mekanika kontinuum Rheologi Mekanika benda padat Mekanika fluida Fisika plasma Ter...

 

blog

Artikel ini mengulas tentang sejenis aplikasi web. Untuk informasi lebih lanjut tentang catatan dari aktivitas web server, lihat server log. Contoh blog di WordPress Blog (dari kata web log[1]) adalah bentuk aplikasi web yang berbentuk tulisan-tulisan (yang dimuat sebagai posting) pada sebuah halaman web. Tulisan-tulisan ini sering kali dimuat dalam urutan isi terbaru dahulu sebelum diikuti isi yang lebih lama, meskipun tidak selamanya demikian. Situs web seperti ini biasanya dapat d...

 

Синелобый амазон

Синелобый амазон Научная классификация Домен:ЭукариотыЦарство:ЖивотныеПодцарство:ЭуметазоиБез ранга:Двусторонне-симметричныеБез ранга:ВторичноротыеТип:ХордовыеПодтип:ПозвоночныеИнфратип:ЧелюстноротыеНадкласс:ЧетвероногиеКлада:АмниотыКлада:ЗавропсидыКласс:Пт�...

Cycling at the 2020 Summer Paralympics – Women's road time trial

Cycling at the2020 Summer ParalympicsRoad cyclingRoad racemenwomenTime trialmenwomenTeam relaymixedTrack cyclingTime trialmenwomenIndividual pursuitmenwomenTeam sprintmixedvte Cycling at the2020 Summer ParalympicsRoad time trialMenWomenBBH1H1–3H2H3H4H4–5H5C1C1–3C2C3C4C4C5C5T1–2T1–2vte The women's road time trial cycling events at the 2020 Summer Paralympics took place on August 31 at Fuji Speedway, Oyama, Japan. There will be seven events taking place over twelve classifications. F...

 

Georgian Soviet Socialist Republic

Union republic of the Soviet Union (1921–1991) Socialist Soviet Republic of Georgia(1921–1936)საქართველოს სოციალისტური საბჭოთა რესპუბლიკა (Georgian)Социалистическая Советская Республика Грузия (Russian)Georgian Soviet Socialist Republic(1936–1990)საქართველოს საბჭოთა სოციალისტური რესპუბ�...

 

Klazomenai

Ancient city KlazomenaiΚλαζομεναί (in Ancient Greek)Coin from Klazomenai depicting a winged boar, 499 BCShown within TurkeyAlternative nameClazomenaeLocationUrla, İzmir Province, TurkeyRegionIoniaCoordinates38°21′29.4″N 26°46′3.3″E / 38.358167°N 26.767583°E / 38.358167; 26.767583TypeSettlement Klazomenai (Ancient Greek: Κλαζομεναί) or Clazomenae was one of the 12 ancient anatolian ionic cities (the others being Chios, Samos, P...

Tommy Skjerven

Questa voce sull'argomento arbitri di calcio norvegesi è solo un abbozzo. Contribuisci a migliorarla secondo le convenzioni di Wikipedia. Tommy Skjerven Informazioni personali Arbitro di Calcio Sezione Kongsvinger Idrettslag Attività nazionale Anni Campionato Ruolo 1996- Tippeligaen Arbitro Attività internazionale 2001-2012 UEFA e FIFA Arbitro Tommy Skjerven (Kaupanger, 25 luglio 1967) è un arbitro di calcio norvegese. Carriera Iniziò la carriera da arbitro nel 1984, diventando un ...

 

Leang Ambe Pacco

Leang Ambe PaccoGua Ambe Pacco, Gua Ambe Paco, Leang Ambe PacoLua error in Modul:Location_map at line 423: Kesalahan format nilai koordinat.LokasiLingkungan Tompobalang, Kelurahan Kalabbirang, Kecamatan Bantimurung, Kabupaten Maros, Sulawesi Selatan, IndonesiaKoordinat04°59'14.8S 119°40'11.2E[1]Geologikarst / batu kapurSitus webvisit.maroskab.go.idcagarbudaya.kemdikbud.go.idkebudayaan.kemdikbud.go.id/bpcbsulsel/ Wisata Gua PrasejarahLeang Ambe Pacco Informasi Lokasi Lingkungan Tompo...

 

Victory Bowl

Victory Bowl NCCAA Victory Bowl LocationVariousOperated1997–presentChampionship affiliationNCCAAConference tie-insNone2022 matchupSouthwestern Assemblies of God vs. Olivet Nazarene (Olivet Nazarene 21–16) The Victory Bowl is the championship football game between schools that sponsor football and are members of the National Christian College Athletic Association and did not qualify for either the NCAA or NAIA playoffs. It is one of the few post-season bowl games for smaller schools. Becau...

George Shaw (biologist)

English botanist and zoologist (1751–1813) George ShawBornGeorge Kearsley Shaw(1751-12-10)10 December 1751Bierton, BuckinghamshireDied22 July 1813(1813-07-22) (aged 61)LondonNationalityEnglishAlma materMagdalen College, Oxford (MA)Scientific careerFieldsBotany, ZoologyInstitutionsUniversity of Oxford George Kearsley Shaw[1] (10 December 1751 – 22 July 1813) was an English botanist and zoologist. Life Shaw was born at Bierton, Buckinghamshire, and was educated at Magdalen...

 

قالب:شريط جانبي التنجيم

جزء من سلسلة مقالات حولالتنجيم خلفية تاريخ التنجيم العلم والتنجيم علم الفلك والتنجيم التقاليد والأنواع والأنظمة المنجمون المنظمات الفلكية الكواكب في علم التنجيم التقاليد التنجيم البابلي علم التنجيم الهلنستي التنجيم في الإسلام خلال العصور الوسطى علم التنجيم الغربي علم ...

 

Instituto Nacional de Enfermedades Neoplásicas

Instituto Nacional de Enfermedades NeoplásicasDr. Eduardo Cáceres GrazianiLocalizaciónPaís Perú PerúLocalidad Av. Angamos Este 252015038 Surquillo, LimaCoordenadas 12°06′44″S 76°59′54″O / -12.112307, -76.998348Datos generalesFundación 4 de diciembre de 1939Construcción ? - ?Financiamiento PúblicoUniversidad Ministerio de Salud del PerúRed hospitalaria Ministerio de Salud del PerúEspecialidad OncologíaSitio web oficial[editar datos en Wikida...

Mahabharata

Major Hindu epic This article is about the Sanskrit epic. For other uses, see Mahabharata (disambiguation). MahabharataManuscript illustration of the Battle of KurukshetraInformationReligionHinduismAuthorVyasaLanguageSanskritPeriodPrincipally compiled in 3rd century BCE–4th century CEChapters18 ParvasVerses200,000Full textMahabharata at Sanskrit Wikisource Mahabharata at English Wikisource Part of a series onHindu scriptures and texts Shruti Smriti List Vedas Rigveda Samaveda Yajurveda Atha...

 

Chaz Bowyer

Chaz Bowyer Raymond Chaz Bowyer (29 September 1926 – 18 June 2008) was a Royal Air Force armaments and explosives instructor who, after he retired from service, wrote and edited over forty books relating to the operations, aircraft, and men of the Royal Flying Corps, Royal Air Force, and Royal Naval Air Service. He also edited for publication the memoirs of the pilots C.P.O. Bartlett, Eric Crundall, and Gwilym H. Lewis. Early life and family Chaz Bowyer was born in Weymouth, Dorset, on 29 ...

 

Baker County, Florida

County in Florida, United States Not to be confused with Baker, Florida. County in FloridaBaker CountyCountyBaker County Courthouse in Macclenny SealLocation within the U.S. state of FloridaFlorida's location within the U.S.Coordinates: 30°19′N 82°16′W / 30.32°N 82.27°W / 30.32; -82.27Country United StatesState FloridaFoundedFebruary 8, 1861Named forJames McNair BakerSeatMacclennyLargest cityMacclennyArea • Total588.97 sq mi (1,5...

Chief of Staff of the French Air and Space Force

Head of the French Air and Space Force Chief of the Air andSpace Force StaffChef d'état-major de l'arméede l'air et de l'espaceHonor flag[1]IncumbentGeneral Stéphane Mille [fr]since 10 September 2021Ministry of the Armed ForcesTypeChief of StaffAbbreviationCEMAAEMember ofChiefs of Staff CommitteeReports toChief of the Defense StaffSeatHexagone Balard, ParisAppointerPresident of the RepublicRequires the Prime Minister's countersignaturePrecursorDirector of Military...

 

Genshiken

GenshikenげんしけんGenreKomedi, potongan kehidupan[1] MangaPengarangShimoku KioPenerbitKodanshaPenerbit bahasa InggrisNA Kodansha ComicsMajalahAfternoonDemografiSeinenTerbit25 April 2002 – 25 Mei 2006Volume9 (Daftar volume) Seri animeSutradaraTakashi IkehataProduserTakaya IbiraAtsushi YamamoriNaoki SakamotoKōji TsukamotoKatsumi YamaguchiSkenarioMichiko YokoteMusikMasanori TakumiStudioPalm StudioPelisensiNA AnimeWorksSaluranasliCTC, TV Saitama, Sun TV, tvk, Kids StationTayang 1...

 

Dog Eat Dog (film, 2016)

Pour les articles homonymes, voir Dog Eat Dog. Cet article est une ébauche concernant un film américain. Vous pouvez partager vos connaissances en l’améliorant (comment ?) selon les conventions filmographiques. Dog Eat Dog Données clés Réalisation Paul Schrader Scénario Matthew Wilder Musique Deantoni ParksNicci Kasper Acteurs principaux Nicolas Cage Willem Dafoe Christopher Matthew Cook Sociétés de production Blue Budgie Films LimitedPure Dopamine Pays de production États-U...

Chayei Sarah

Pengkebumian Sarah (engravir karya Gustave Doré dari Alkitab La Sainte tahun 1865) Chayei Sarah, Chaye Sarah, atau Hayye Sarah (חַיֵּי שָׂרָה — Ibrani untuk kehidupan Sarah, kata-kata pertama dalam parsyah tersebut) adalah bacaan Taurat Mingguan (פָּרָשָׁה, parashah) kelima dalam siklus bacaan Taurat Yahudi tahunan. Bacaan tersebut meliputi Kejadian 23:1–25:18. Parsyah tersebut mengisahkan cerita negosiasi Abraham untuk membeli tempat pengkebumian istrinya Sarah dan ...

 

Премниц

ГородПремницPremnitz Герб 52°31′59″ с. ш. 12°19′59″ в. д.HGЯO Страна  Германия Земля Бранденбург Район Хафельланд (район) История и география Город с 1962 Площадь 45,42 км² Высота центра 30 м Часовой пояс UTC+1:00, летом UTC+2:00 Население Население 8368 человек (2020) Цифровые иде�...