Erősen összefüggő komponens

Ebben a gráfban megjelöltük az erősen összefüggő komponenseket

A matematika, azon belül a gráfelmélet területén egy irányított gráf akkor erősen összefüggő (strongly connected vagy diconnected), ha bármely csúcs bármely másik csúcsból elérhető. Egy irányított gráf erősen összefüggő komponensei, röviden erős komponensei (strongly connected components vagy diconnected components) a gráf olyan részgráfokra való felbontását adják, mely részgráfok maguk is erősen összefüggőek. Egy gráf erős összefüggőségének tesztelése, illetve erősen összefüggő komponenseinek megkeresése lineáris időben elvégezhető feladat.

Definíciók

Egy irányított gráf erősen összefüggő, ha bármely két csúcsa között mindkét irányban létezik (irányított) út. A G irányított gráfban, még ha nem is erősen összefüggő, ha u és v csúcsok között mindkét irányban létezik út, akkor a két csúcs erősen összefügg egymással.

Az erős összefüggőség bináris relációja egy ekvivalenciareláció, melynek ekvivalenciaosztályai által meghatározott feszített részgráfok neve erősen összefüggő komponensek. Ezzel ekvivalens megfogalmazás, hogy egy G irányított gráf erősen összefüggő komponense olyan részgráf, mely erősen összefüggő, és a következő tulajdonság szerint maximális: G bármely további csúcsának vagy élének hozzáadásával megszűnne az erős összefüggősége. Az erősen összefüggő komponensek G csúcshalmazának felbontását alkotják.

A sárga irányított körmentes gráf a kék irányított gráf kondenzálásával jött létre. Ez úgy történik, hogy a kék gráf minden erősen összefüggő komponensét egy-egy sárga csúcsba húzzuk össze.

Ha minden erősen összefüggő komponenst összehúzunk egy-egy csúcsba, az eredményül kapott irányított körmentes gráfot a G gráf kondenzációjának nevezzük. Egy irányított gráf pontosan akkor körmentes, ha nincsenek egynél több csúcsból álló erősen összefüggő részgráfjai – hiszen egy irányított kör erősen összefüggő, és minden nemtriviális erősen összefüggő komponens legalább egy irányított kört tartalmaz.

Algoritmusok

Számos algoritmus létezik az erősen összefüggő komponensek lineáris időben történő azonosítására.

  • A Kosaraju-algoritmus két menetben futtat mélységi keresést. Az első menet az eredeti gráfon fut annak meghatározására, hogy a második mélységi keresés külső ciklusa milyen sorrendben vizsgálja meg a csúcsokat, hogy járt-e már ott, és rekurzív vizsgálatba kezdjen, ha még nem. A második mélységi keresés az eredeti gráf transzponáltján (megfordításán) történik, és minden rekurzív keresési lépésben egy új erősen összefüggő komponenst tár fel.[1] Nevét S. Rao Kosarajuról kapta, aki 1978-ban leírta (de nem publikálta eredményeit); ezt 1981-ben Micha Sharir tette meg.[2]
  • A Tarjan-algoritmus, amit 1972-ben Robert Tarjan publikált,[3] egyetlen menetben végez mélységi keresést. Egy veremben tárolja azokat a csúcsokat, melyekhez még nem lett komponens hozzárendelve, és minden csúcshoz kiszámítja a hozzá tartozó „alacsony számot” (low number) – a csúcs egy leszármazottjából elérhető legmagasabb ősének indexe –, melyet annak eldöntésére használ, hogy csúcsok egy halmazát mikor kell elővennie a veremből és elhelyezni egy új komponensben.
  • Az útalapú erős komponens-algoritmus Tarjan algoritmusához hasonlóan egyetlen mélységi keresést végez, de két vermet használ. Az egyik verem tartja számon a komponenshez még nem rendelt csúcsokat, a másik pedig a mélységi keresés aktuális útját. Ennek az algoritmusnak az első lineáris idejű változatát Edsger W. Dijkstra publikálta 1976-ban.[4]

Bár Kosaraju algoritmusa egyszerűbben megérthető, a Tarjan-féle és az útalapú algoritmus kettő helyett csak egy mélységi keresést igényel.

Alkalmazásai

Egy irányított gráf (hálózat) "csokornyakkendő diagrammja". Gyakran egy hálózatnak egy komoly része egyetlen erősen összefüggő komponensben található. Az itt található százalékok a Világháló 2000-ben történt felméréséből származnak.

Az erősen összefüggő komponenseket megtaláló algoritmusokkal meg lehet oldani 2-kielégíthetőségi (2-SAT) problémákat is (ezek Boole-változók olyan rendszerei, melyekben változópárokat együtt vizsgálunk): ahogy (Aspvall, Plass & Tarjan 1979) megmutatta, egy 2-kielégíthetőségi probléma pontosan akkor nem oldható meg, ha létezik olyan v változó, amire v és komplementere is a probléma következtetési gráfjának ugyanabban az erősen összefüggő komponensében található.[5]

Az erősen összefüggő komponensek felhasználhatók a Dulmage–Mendelsohn-felbontás kiszámításában, ez a páros gráf éleinek osztályozása aszerint, hogy szerepelnek-e a gráf valamely teljes párosításában.[6]

Kapcsolódó eredmények

Egy irányított gráf pontosan akkor erősen összefüggő, ha létezik fülfelbontása, tehát élei particionálhatók irányított utak és körök olyan sorozatába, hogy a sorozat első részgráfja egy kör, és minden rákövetkező részgráf vagy egy olyan kör, ami egy csúcsában közös a megelőző részgráfokkal, vagy olyan út, ami két végpontjában közös a megelőző részgráfokkal.

A Robbins-tétel szerint egy irányítatlan gráfnak pontosan akkor létezik azt erősen összefüggővé tevő irányítása, ha 2-szeresen élösszefüggő. Ennek az egyik bizonyítása szerint meg kell keresni az eredeti irányítatlan gráf egy fülfelbontását, és minden fület konzisztensen kell irányítani.[7]

Kapcsolódó szócikkek

Jegyzetek

  1. Thomas H. Cormen, Charles E. Leiserson, Ronald L. Rivest, and Clifford Stein. Introduction to Algorithms, Second Edition. MIT Press and McGraw-Hill, 2001. ISBN 0-262-03293-7. Section 22.5, pp. 552–557.
  2. Micha Sharir. A strong connectivity algorithm and its applications to data flow analysis. Computers and Mathematics with Applications 7(1):67–72, 1981.
  3. Tarjan, R. E. (1972), "Depth-first search and linear graph algorithms", SIAM Journal on Computing 1 (2): 146–160, DOI 10.1137/0201010
  4. Dijkstra, Edsger (1976), A Discipline of Programming, NJ: Prentice Hall, Ch. 25.
  5. Aspvall, Bengt; Plass, Michael F. & Tarjan, Robert E. (1979), "A linear-time algorithm for testing the truth of certain quantified boolean formulas", Information Processing Letters 8 (3): 121–123, DOI 10.1016/0020-0190(79)90002-4.
  6. Dulmage, A. L. & Mendelsohn, N. S. (1958), "Coverings of bipartite graphs", Canad. J. Math. 10: 517–534, DOI 10.4153/cjm-1958-052-0.
  7. Robbins, H. E. (1939), "A theorem on graphs, with an application to a problem on traffic control", American Mathematical Monthly 46: 281–283, DOI 10.2307/2303897.

Fordítás

  • Ez a szócikk részben vagy egészben a Strongly connected component című angol Wikipédia-szócikk ezen változatának fordításán alapul. Az eredeti cikk szerkesztőit annak laptörténete sorolja fel. Ez a jelzés csupán a megfogalmazás eredetét és a szerzői jogokat jelzi, nem szolgál a cikkben szereplő információk forrásmegjelöléseként.

További információk

Read other articles:

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

 

Municipio de Transit Municipio Municipio de TransitUbicación en el condado de Sibley en Minnesota Ubicación de Minnesota en EE. UU.Coordenadas 44°34′33″N 94°18′19″O / 44.575833333333, -94.305277777778Entidad Municipio • País Estados Unidos • Estado  Minnesota • Condado SibleySuperficie   • Total 92.27 km² • Tierra 90.66 km² • Agua (1.74 %) 1.6 km²Altitud   • Media 312 m s. n. m.Población...

 

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

Het kasteel Sarolea in Cheratte De Sarolea de Cheratte was een Zuid-Nederlandse adellijke familie. In de 19e bezaten ze onder meer concessies voor steenkolenwinning in Cheratte. Na verkoop van deze concessie werd de Steenkolenmijn van Hasard opgestart. Geschiedenis en genealogie Nicolas de Sarolea de Cheratte (1584-1658) trouwde met Elisabeth Heurkeau (1584-1673). Gilles de Sarolea de Cheratte (1617-1695), steenkolenontginner, trouwde met Catherine de Piroulle (1624-1696). In 1643 bouwde hij ...

 

هذه المقالة يتيمة إذ تصل إليها مقالات أخرى قليلة جدًا. فضلًا، ساعد بإضافة وصلة إليها في مقالات متعلقة بها. (يوليو 2019) C11H20O10 هي صيغة كيميائية[1] تحتوي على 11 ذرة من الكربون و20 ذرة من الهيدروجين و10 ذرات من الأكسجين وتبلغ كتلتها المولية 312.2705 غ.مول-1. ومن المركبات الكيميائية الت...

 

?Златка чорна Біологічна класифікація Домен: Еукаріоти (Eukaryota) Царство: Тварини (Animalia) Тип: Членистоногі (Arthropoda) Клас: Комахи (Insecta) Підклас: Крилаті комахи (Pterygota) Інфраклас: Новокрилі (Neoptera) Надряд: Голометабола (Holometabola) Ряд: Жуки (Coleoptera) Підряд: Всеїдні жуки (Polyphaga) Інфраряд: Еля

Courage award in Canada For other uses, see Cross of Valour. AwardCross of ValourBadge of the Cross of ValourTypeState decorationAwarded forActs of the most conspicuous courage in circumstances of extreme peril[1]Presented byThe monarch of CanadaPost-nominalsCVStatusCurrently awardedEstablished1 May 1972First awarded20 July 1972Last awarded4 May 2006Created byElizabeth IITotal20[2]Total awarded posthumously5[2]Ribbon bar of the Cross of Valour PrecedenceNext (high...

 

Artūrs ŽagarsŽagars dengan Tim nasional bola basket Latvia pada tahun 2023Free agentPosisiPoint guard / Shooting guardInformasi pribadiLahir21 April 2000 (umur 23)Riga, LatviaKebangsaanLatviaTinggi1,90 m (6 ft 3 in)Berat78 kg (172 pon)Informasi karierDraf NBA2022 / Tidak didrafKarier bermain2017–sekarangRiwayat karier2017–2022Joventut Badalona2018–2019→CB Prat2021→Kalev/Cramo2022→Löwen Braunschweig2022–2023Nevėžis Kėdainiai Prestasi dan penca...

 

The UCLA Language Materials Project (LMP) maintained a web resource about teaching materials for some 150 languages that are less commonly taught in the United States. The project, funded by the U.S. Department of Education, was created in 1992. It is part of the UCLA Center for World Languages. Funding was terminated in 2014[1] and the Language Materials Project website deactivated. Bibliographic database of teaching materials The website provided full bibliographic information for o...

Agency of Kansas, U.S. Kansas Department of CorrectionsKDOCAgency overviewEmployees3,549Jurisdictional structureOperations jurisdictionKansas, USAEl DoradoHutchinsonLansingLeavenworthMJRCFTopekaclass=notpageimage| Kansas Prisons — green=state, red=private (Hover mouse over pog to popup clickable link)Map of Kansas Department of Corrections's jurisdictionGeneral natureLocal civilian policeOperational structureHeadquartersTopeka, KansasAgency executiveJeff Zmuda, Secretary of CorrectionsWebsi...

 

Municipality in Bagmati Province, NepalNagarjun Municipality नागार्जुन नगरपालिकाMunicipalityStatues of five meditating Buddha at Amitabha MonasteryNagarjun MunicipalityLocation in NepalShow map of Bagmati ProvinceNagarjun MunicipalityNagarjun Municipality (Nepal)Show map of NepalCoordinates: 27°43′57″N 85°15′24″E / 27.73250°N 85.25667°E / 27.73250; 85.25667Country   NepalProvinceBagmati ProvinceDistrictKath...

 

Enpiperate Names Preferred IUPAC name 1-Methylpiperidin-4-yl hydroxydi(phenyl)acetate Identifiers CAS Number 3608-67-1 Y 3D model (JSmol) Interactive image ChemSpider 69594 N ECHA InfoCard 100.020.704 IUPHAR/BPS 352 PubChem CID 77157 UNII QWK86805EB Y CompTox Dashboard (EPA) DTXSID20189664 InChI InChI=1S/C20H23NO3/c1-21-14-12-18(13-15-21)24-19(22)20(23,16-8-4-2-5-9-16)17-10-6-3-7-11-17/h2-11,18,23H,12-15H2,1H3 NKey: UGYPGJCVNPPUPE-UHFFFAOYSA-N NInChI=1/C20H23NO3/...

I've Got You Under My Skin kan verwijzen naar: I've Got You Under My Skin (nummer), muzieknummer van Cole Porter, door velen gecoverd I've Got You Under My Skin (Charmed), aflevering uit de Amerikaanse televisieserie Charmed Bekijk alle artikelen waarvan de titel begint met I've Got You Under My Skin of met I've Got You Under My Skin in de titel. Dit is een doorverwijspagina, bedoeld om de verschillen in betekenis of gebruik van I've Got You Under My Skin inzichtelijk...

 

Собор Сибирских святых Икона «Собор Сибирских святых» Тип Праздник Русской православной церкви Установлен в память о православных подвижниках Сибири Дата 10 (23) июня См. также: Собор (праздник) Собор Сибирских святых — праздник в честь святых православных подвижник...

 

For the post office in Lewistown, Montana, see Lewistown Main Post Office. United States historic placeU.S. Post Office–Lewiston MainU.S. National Register of Historic Places United States Post OfficeShow map of MaineShow map of the United StatesLocation49 Ash St., Lewiston, MaineCoordinates44°5′47″N 70°12′57″W / 44.09639°N 70.21583°W / 44.09639; -70.21583Area0.5 acres (0.20 ha)Built1933Built byCoath & GossArchitectJames A. WetmoreArchitectural&#...

Рафаельітал. Raffaello Sanzio АвтопортретІм'я при народженні Рафаель СантіНародився 28 березня 1483(1483-03-28) Урбіно (область Марке)Помер 6 квітня 1520(1520-04-06) (37 років) Рим·серцева недостатністьПоховання Римський Пантеон[1] :  Країна  Священна Римська імперіяНаціональність і...

 

2014 greatest hits album by TokioHeartGreatest hits album by TokioReleasedJuly 16, 2014 (2014-07-16)Recorded1994–2014LanguageJapaneseLabelJ StormTokio chronology 17(2012) Heart(2014) Singles from Heart LyricReleased: February 20, 2013 Heart is the third greatest hits album by Japanese band Tokio. It was released on July 16, 2014, through J Storm.[1] The album debuted atop the Oricon Albums Chart, selling 41,000 copies.[2][3] It became Tokio's s...

 

Ski resort in California, United States This article has multiple issues. Please help improve it or discuss these issues on the talk page. (Learn how and when to remove these template messages) This article possibly contains original research. Please improve it by verifying the claims made and adding inline citations. Statements consisting only of original research should be removed. (June 2017) (Learn how and when to remove this template message) This article needs additional citations for v...

Barrier separating side chapels from the rest of the church Parclose screen, c. 1530, of the Moorhayes Chapel, Cullompton Church, Devon, England. Looking north-west from within the chancel. Part of the brightly decorated, higher, chancel screen is visible beyond. A parclose screen is a screen or railing used to enclose or separate-off a chantry chapel,[1] tomb or manorial chapel, from public areas of a church, for example from the nave or chancel. It should be distinguished from the c...

 

Fountain and sculpture in Salem, Oregon, U.S. Hatfield FountainThe fountain in 2008Artist Tom Hardy Lawrence Halprin Scott Stickney Year1989 (1989)TypeFountain, sculptureMediumFountain: Concrete, stoneSculpture: Bronze, steelDimensions4.0 m (13 ft); 7.0 m diameter (23 ft)ConditionWell maintained (1993)LocationSalem, Oregon, United StatesCoordinates44°56′06″N 123°01′53″W / 44.93509°N 123.03127°W / 44.93509; -123.03127OwnerWil...

 

Strategi Solo vs Squad di Free Fire: Cara Menang Mudah!