Graphe connexe

Cet article est une ébauche concernant les mathématiques.

Vous pouvez partager vos connaissances en l’améliorant (comment ?) selon les recommandations des projets correspondants.

En théorie des graphes, un graphe non orienté est dit connexe s'il est d'un seul tenant.

Définitions

Un graphe non orienté $G=(V,E)$ est dit connexe si quels que soient les sommets $u$ et $v$ de $V$ , il existe une chaîne reliant $u$ à $v$ .

Un sous-graphe connexe maximal d'un graphe non orienté quelconque est une composante connexe de ce graphe.

Pour un graphe orienté, on dit qu'il est :

de faible connexité, si en oubliant l'orientation des arêtes, le graphe est connexe ;
de connexité unilatérale, si pour toute paire de sommets (u, v), il existe un chemin orienté allant de u à v ou de v à u ;
de forte connexité s'il existe un chemin orienté depuis tout sommet u vers tout sommet v.

Propriétés

Une composante connexe d'un graphe est un sous-graphe connexe de ce graphe.
Un arbre déconnecté est une forêt.
Un graphe connexe à $n$ sommets possède au moins $n-1$ arêtes.
Un graphe connexe à $n$ sommets ayant exactement $n-1$ arêtes est un arbre.
Un graphe dont toutes les composantes connexes sont des arbres est une forêt.
Un graphe à $n$ sommets avec $k$ composantes connexes possède au moins $n-k$ arêtes.
Si on note $L$ la matrice laplacienne d'un graphe $G$ , alors la multiplicité de la valeur propre 0 de $L$ est le nombre de composantes connexes de $G$ .

Algorithmes

L’algorithme de parcours en profondeur permet de déterminer si un graphe est connexe ou non. Dans le cas d'un graphe construit de façon incrémentale, on peut utiliser des algorithmes de connexité basés sur des pointeurs pour déterminer si deux sommets sont dans la même composante connexe.

Complexité théorique

On s'intéresse à savoir si un graphe non orienté est connexe. Dès 1979, on savait qu'il était dans une classe probabiliste en espace logarithmique^[1]. Reingold, dans un article de 2008, a démontré que le problème d'accessibilité dans un graphe non orienté est dans LOGSPACE^[2], donc savoir si un graphe est connexe est aussi dans LOGSPACE. Quand on présente le graphe comme une union de cycles, le problème est NC¹-complet^[3].

Notes et références

↑ Romas Aleliunas, Richard M. Karp, Richard J. Lipton et Laszlo Lovasz, « Random Walks, Universal Traversal Sequences, and the Complexity of Maze Problems », Proceedings of the 20th Annual Symposium on Foundations of Computer Science, IEEE Computer Society, sFCS '79,‎ 1979, p. 218–223 (DOI 10.1109/SFCS.1979.34, lire en ligne, consulté le 30 mai 2019)
↑ Omer Reingold, « Undirected connectivity in log-space », Journal of the ACM, vol. 55, n^o 4,‎ 2008, p. 1–24 (lire en ligne)
↑ Stephen A Cook et Pierre McKenzie, « Problems complete for deterministic logarithmic space », Journal of Algorithms, vol. 8, n^o 3,‎ 1^er septembre 1987, p. 385–394 (ISSN 0196-6774, DOI 10.1016/0196-6774(87)90018-6, lire en ligne, consulté le 30 mai 2019)

Voir aussi

Read other articles:

Charmer (Kings of Leon song)

2007 single by Kings of LeonCharmerSingle by Kings of Leonfrom the album Because of the Times ReleasedOctober 29, 2007GenreHard rock, garage rock, indie rockLength2:56LabelColumbiaSongwriter(s)Kings of LeonProducer(s)Ethan JohnsAngelo PetragliaKings of Leon singles chronology Fans (2007) Charmer (2007) Sex on Fire (2008) Charmer is a song by American rock band Kings of Leon, and is the third single released from their 2007 album Because of the Times. It is the second track on the album. The s...

Вавилонская башня

У этого термина существуют и другие значения, см. Вавилонская башня (значения). Вавилонская башня Местонахождение Вавилон, Вавилония Технические параметры Медиафайлы на Викискладе Древнерусская миниатюра из «Христианской топографии» Косьмы Индикоплова (1539) Вавило́...

الرابطة الإسلامية في إيطاليا

هذه المقالة يتيمة إذ تصل إليها مقالات أخرى قليلة جدًا. فضلًا، ساعد بإضافة وصلة إليها في مقالات متعلقة بها. (فبراير 2016) الرابطة الإسلامية في إيطاليا البلد إيطاليا المقر الرئيسي ميلانو الاهتمامات الإسلام تعديل مصدري - تعديل الرابطة الإسلامية في إيطاليا هي جمعية إيطال�...

Résistivité

La résistivité d'un matériau, généralement symbolisée par la lettre grecque rho (ρ), représente sa capacité à s'opposer à la circulation du courant électrique. Elle correspond à la résistance[N 1] d'un tronçon de matériau d'un mètre de longueur et d'un mètre carré de section et est exprimée en ohms mètres (ou ohms-mètres), de symbole Ω m (ou Ω⋅m). On utilise aussi : le Ω mm2/m = 10−6 Ω m ; le μΩ cm = 10−8 Ω m. L'�...

Resident Evil: The Umbrella Chronicles

2007 video gameResident Evil: The Umbrella ChroniclesNorth American Wii box artDeveloper(s)CapcomCaviaPublisher(s)CapcomDirector(s)Yasuhiro SetoHiroaki KotakeProducer(s)Masachika KawataToru TakahashiDesigner(s)Naoshige KamamotoDaichi KurumiyaWriter(s)Yasuhiro SetoHaruo MurataComposer(s)Masafumi TakadaJun FukudaSeriesResident EvilPlatform(s)Wii, PlayStation 3[2]Release November 13, 2007 WiiNA: November 13, 2007JP: November 15, 2007EU: November 30, 2007AU: December 13, 2007KO: June 20,...

Oga, Akita

Oga 男鹿市KotaDari atas ke bawah, kiri ke kanan : Bunga Hydrangea di Kuil Unshōji, Panorama senja di Pantai Unosaki, Namahage, Pantai Nyūdōzaki, Oga Aquarium Gao, Gunung Kanpu, Kuil Akagami, Godzilla Rock, Laguna Ninome dan Teluk Toga. BenderaEmblemLokasi Oga di Prefektur AkitaOgaLokasi di JepangKoordinat: 39°53′12″N 139°50′51″E / 39.88667°N 139.84750°E / 39.88667; 139.84750Koordinat: 39°53′12″N 139°50′51″E / 39.88667°N...

Overseas landholdings of the Marcos family

A 2005 image of 40 Wall Street, one of four Manhattan buildings purchased by the Marcoses in the early 1980s The overseas landholdings of the Marcos family, which the Philippine government[1][2] and the United Nations System's Stolen Asset Recovery Initiative[3] consider part of the $5 billion to $13 billion ill-gotten wealth of Ferdinand and Imelda Marcos, are said to be distributed worldwide in places including California, Washington, New York, Rome, Vienna, Austral...

South Sumatra

Province of Indonesia Province in IndonesiaSouth Sumatra Sumatera SelatanProvinceProvince of South Sumatra Coat of armsNickname(s): Bumi Sriwijaya (Indonesian)Land of SrivijayaMotto(s): Bersatu Teguh (Indonesian)Stand TogetherLocation of South Sumatra in IndonesiaOpenStreetMapCoordinates: 2°45′S 103°50′E / 2.750°S 103.833°E / -2.750; 103.833CountryIndonesiaCapitaland largest cityPalembangEstablished15 May 1946Government • BodySouth Sumatra...

Flight shame

Social movement that discourages airline flying Shame of flying redirects here. For the anxiety disorder, see Fear of flying. An A320 of Air Sweden Flight shame or flygskam is an anti-flying social movement, with the aim of reducing the environmental impact of aviation. Flight shame refers to an individual's uneasiness over engaging in consumption that is energy-intense and climatically problematic. It also reflects on air travelers as people involved in socially undesirable activities, and a...

Tangier Ibn Battouta Airport

Airport in Morocco Tangier Ibn Battuta Airportمطار طنجة ابن بطوطة (Arabic)IATA: TNGICAO: GMTTSummaryAirport typePublicOperatorONDALocationTangier, MoroccoFocus city forAir Arabia MarocRoyal Air MarocElevation AMSL62 ft / 19 mCoordinates35°43′37″N 005°55′01″W / 35.72694°N 5.91694°W / 35.72694; -5.91694Websiteonda.maMapTNGLocation of airport in MoroccoRunways Direction Length Surface m ft 10/28 3,500 11,483 Asphalt 7/25 (CL...

Forza Horizon 4

Forza Horizon 4videogiocoPiattaformaXbox One, Microsoft Windows, Xbox Series X/S Data di pubblicazioneXbox One, Windows: 2 ottobre 2018 Xbox Series X/S: 10 novembre 2020 GenereSimulatore di guida OrigineRegno Unito SviluppoPlayground Games PubblicazioneMicrosoft Game Studios Modalità di giocoGiocatore singolo, multigiocatore Periferiche di inputGamepad, mouse, tastiera Motore graficoXbox OneForzaTech engineForza Motorsport 7(Modificato)Drivatar(Intelligenza Artificiale) PCForzaTech e...

المركز الجامعي (إليزي)

يفتقر محتوى هذه المقالة إلى الاستشهاد بمصادر. فضلاً، ساهم في تطوير هذه المقالة من خلال إضافة مصادر موثوق بها. أي معلومات غير موثقة يمكن التشكيك بها وإزالتها. (أبريل 2020) هذه المقالة يتيمة إذ تصل إليها مقالات أخرى قليلة جدًا. فضلًا، ساعد بإضافة وصلة إليها في مقالات متعلقة بها. ...

The Narrows (Pennsylvania)

Water gap in Pennsylvania The Narrows Bridge in 1997 Another view looking west in 1982 The Narrows is a water gap where the Raystown Branch of the Juniata River passes through Evitts Mountain in Bedford County, Pennsylvania. Both U.S. Route 30 (part of the Lincoln Highway) and the Pennsylvania Turnpike pass through the gap. It is located in the townships of Snake Spring and Bedford. Geology A major group of east-west trending faults and the erosional force of the Raystown Branch of the Juniat...

Buxus sempervirens

Species of flowering plants in the box family Buxus sempervirens Mature specimen Scientific classification Kingdom: Plantae Clade: Tracheophytes Clade: Angiosperms Clade: Eudicots Order: Buxales Family: Buxaceae Genus: Buxus Species: B. sempervirens Binomial name Buxus sempervirensL. Distribution range of Buxus sempervirens Buxus sempervirens, the common box, European box, or boxwood, is a species of flowering plant in the genus Buxus, native to western and southern Europe, northwest Afr...

面積

この記事は検証可能な参考文献や出典が全く示されていないか、不十分です。出典を追加して記事の信頼性向上にご協力ください。（このテンプレートの使い方）出典検索?: 面積 – ニュース · 書籍 · スカラー · CiNii · J-STAGE · NDL · dlib.jp · ジャパンサーチ · TWL（2017年6月）この記事は英語版の対応するページを翻訳すること�...

Unione Sportiva Alessandria Calcio 1912 2020-2021

Voce principale: Unione Sportiva Alessandria Calcio 1912. US Alessandria Calcio 1912Stagione 2020-2021Sport calcio Squadra Alessandria Allenatore Angelo Gregucci (1ª-19ª) Moreno Longo (20ª-38ª e play-off) All. in seconda Marco Martini (1ª-19ª) Dario Migliaccio (20ª-38ª e play-off) Presidente Luca Di Masi Serie C2º e promossa (vince i play-off) Coppa ItaliaSecondo turno Maggiori presenzeCampionato: Arrighini (36)Totale: Arrighini (44) Miglior marcatoreCampionato: Eusepi (11)Tota...

L'etrusco uccide ancora

Questa voce sull'argomento film thriller è solo un abbozzo. Contribuisci a migliorarla secondo le convenzioni di Wikipedia. Segui i suggerimenti del progetto di riferimento. L'etrusco uccide ancoraTitoli del trailerPaese di produzioneItalia, Germania, Jugoslavia Anno1972 Durata105 Generethriller, giallo, orrore RegiaArmando Crispino SoggettoLucio Battistrada, Armando Crispino SceneggiaturaLucio Battistrada, Armando Crispino, Casa di produzioneMondial Te.Fi, Inex Film, C...

楊文愷

楊文愷楊文愷（1883年—1965年6月）字建章，直隷省順天府永清县人，清末、中華民国军事将领、政治家。[1][2] 生平楊文愷是清朝秀才。[1]（但据其孙杨林说，楊文愷仅随父亲念过私塾。[3]）後赴日本留学，毕业于陸軍士官学校第6期步兵科。归国後，楊文愷历任禁衛軍一等参謀、直隷都督府軍務課課長、湖北督軍公署軍務課課長兼漢陽兵工廠总办等�...

Alexander Selkirk

18th-century Scottish sailor and castaway Alexander SelkirkClad in goatskins, Selkirk awaits rescue in a sculpture by Thomas Stuart Burnett (1885)Born1676Lower Largo, Fife, ScotlandDied13 December 1721 (aged 45)Cape Coast, Gold CoastNationalityScottish and British (after 1707)OccupationSailorKnown forInspiring Robinson CrusoeParent(s)John Selcraig, Euphan Mackie Alexander Selkirk (1676 – 13 December 1721) was a Scottish privateer and Royal Navy officer who spent four ...

Sextus Pompey

Roman politician and general (c. 67–35 BC) Sextus Pompeius redirects here. For other uses, see Sextus Pompeius (disambiguation). Sextus PompeyPortrait of Sextus Pompey on a gold aureus issued in Sicily, 37/6 BC. The inscription says Mag(nus) Pius Imp(erator) Iter(um), meaning Magnus Pius, Imperator Twice Over.Personal detailsBornc. 67 BC[1]Died35 BC (aged around 32)Miletus, Asia, Roman RepublicNationalityRomanChildrenPompeiaRelativesPompey (father)Mucia Tertia (mother)Gnaeus P...

Chicago 'L'

/profillengkap.com/index.php/article/Carlsbad Caverns National Park

/profillengkap.com/index.php/article/Carlock, Illinois

/profillengkap.com/index.php/article/Gannes

/profillengkap.com/index.php/article/1951 Princeton Tigers baseball team

العلاقات التونسية السنغافورية