Thành phần liên thông mạnh

Đối với các định nghĩa khác, xem Liên thông.
Một đồ thị với các thành phần liên thông mạnh đã được đánh dấu

Một đồ thị có hướng là liên thông mạnh nếu như có đường từ bất kì đỉnh nào tới bất kì đỉnh nào khác. Một thành phần liên thông mạnh của một đồ thị có hướng là một đồ thị con tối đại liên thông mạnh. Nếu mỗi thành phần liên thông mạnh được co lại thành một đỉnh, thì đồ thị sẽ trở thành một đồ thị có hướng không có chu trình.

Thuật toán Kosaraju, thuật toán Tarjan, và thuật toán Gabow đều có thể tìm các thành phần liên thông mạnh của một đồ thị cho trước trong thời gian tuyến tính. Tuy nhiên, các thuật toán của Tarjan và Gabow thường được sử dụng nhiều hơn do chúng chỉ cần thực hiện tìm kiếm theo chiều sâu một lần trong khi thuật toán của Kosaraju cần hai lần.

Thuật toán tìm thành phần liên thông mạnh có thể được dùng để giải bài toán thỏa mãn biểu thức logic trong đó mỗi điều kiện có hai biến số. Theo Aspvall, Plass, và Tarjan đã chứng minh năm 1979[1], một biểu thức logic với các điều kiên có kích thước 2 là không thể thỏa mãn được khi và chỉ khi tồn tại một biến v sao cho v và phủ định của v nằm trong cùng một thành phần liên thông mạnh trong đồ thị quan hệ của biểu thức đó.

Ghi chú

  1. ^ 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.

Read other articles:

Messier 34

Messier 342MASS Foto M34 (diambil dengan inframerah)Data pengamatan (J2000.0 epos)KelasI,3,mRasi bintangPerseus[1]Asensio rekta 02j 42.1m[2]Deklinasi +42° 46′[2]Jarak1,500 light year (470 pc[3])Magnitudo tampak (V)5.5[1]Dimensi tampak (V)35.0′[1]Karakteristik fisikRadius7 ly[butuh rujukan]Perkiraan umur200–250 million years[3]Nama lainNGC 1039, OCl 382, C 0238+425[2]Lihat pula: Gu...

 

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

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

 

Telapristone

Chemical compound TelapristoneClinical dataOther namesCDB-4124; Proellex; Progenta; 17β-(Acetyloxy)-11β-[4-(dimethylamino)phenyl]-17α-(2-methoxyacetyl)estra-4,9-dien-3-oneDrug classSelective progesterone receptor modulatorLegal statusLegal status Investigational Identifiers IUPAC name [(8S,11R,13S,14S,17R)-11-[4-(Dimethylamino)phenyl]-17-(2-methoxyacetyl)-13-methyl-3-oxo-1,2,6,7,8,11,12,14,15,16-decahydrocyclopenta[a]phenanthren-17-yl] acetate CAS Number198414-31-2PubChem CID9806190PubChem...

Tzniut

This article includes a list of general references, but it lacks sufficient corresponding inline citations. Please help to improve this article by introducing more precise citations. (June 2023) (Learn how and when to remove this message) Modesty and discretion, as well as a group of Jewish laws pertaining to conduct Part of a series onJudaism     Movements Orthodox Haredi Hasidic Modern Conservative Conservadox Reform Karaite Reconstructionist Renewal Humanistic Haymanot ...

 

Liverpool Cathedral

Anglican cathedral in Liverpool, England For the Roman Catholic cathedral in the same city, see Liverpool Metropolitan Cathedral. Church in Liverpool, United KingdomLiverpool CathedralCathedral Church of Christ in LiverpoolLiverpool Anglican Cathedral, St James's MountLiverpool CathedralShown within Liverpool53°23′51″N 2°58′23″W / 53.39750°N 2.97306°W / 53.39750; -2.97306LocationLiverpoolCountryUnited KingdomDenominationChurch of EnglandTraditionCentral chu...

 

Trap Them

American hardcore punk band Trap ThemRyan McKenney performing at the Knitting Factory, BrooklynBackground informationAlso known asTrap Them + Kill Them, 77+K7OriginSalem, New Hampshire, United StatesGenres Grindcore crust punk metalcore hardcore punk Years active2001–2017LabelsProsthetic, Southern Lord, Trash Art!, DeathwishPast membersRyan McKenneyBrian IzziBrad FickeisenGalen BaudhuinStephen LaCourMike JustianMike SharpScott DeFuscoNat CoghlanChris MaggioWebsitehttp://www.trapthem.net...

Isla Puná

Isla Puná Ubicación geográficaOcéano Océano PacíficoCoordenadas 2°50′00″S 80°08′00″O / -2.8333333333333, -80.133333333333Ubicación administrativaPaís Ecuador EcuadorProvincia GuayasCantón GuayaquilCaracterísticas generalesSuperficie 919Longitud 51 kmAnchura máxima 26 kmPunto más alto 253 mPoblaciónPoblación 6500 hab.  ()Densidad 7,6 hab./km²Otros datosLargo 51 kmAncho 26 kmMapa de localización Isla Puná Ubicación (Ecuador). ...

 

Ducato di Calabria

Voce principale: Storia della Calabria. Mappa dell'Italia all'inizio del IX secolo. Stemma dei duchi di Calabria, usato al tempo in cui era la casa d'Aragona, a governare il regno di Napoli Il Ducato di Calabria (successivamente Thema di Calabria) fu un possedimento romeo in Italia, che comprendeva inizialmente il Salento e la Calabria, e successivamente solo la parte meridionale di quest'ultima. Dal 1061 divenne un possedimento normanno, retto dal Duca di Calabria. Indice 1 Premesse e nasci...

 

Sister, Sister (film 1982)

Sister, SisterBerkas:SisterSister1982.jpgTitle card.GenreDramaFamilyDitulis olehMaya AngelouSutradaraJohn BerryPemeranDiahann CarrollIrene CaraRosalind CashDick Anthony WilliamsPaul WinfieldPenggubah lagu temaAlex NorthNegara asalUnited StatesBahasa asliEnglishProduksiProduser eksekutifIrv WilsonProduserMaya AngelouJohn BerryDennis Berry (associate producer)SinematografiGayne RescherPenyuntingArt SeidDurasi98 minutesRumah produksi20th Century Fox TelevisionDistributorNBCAnggaranUS $50,000Ril...

槍彈辯駁 希望學園與絕望高中生

  关于續作，請見「超級槍彈辯駁2 再會了絕望學園」。   关于外傳，請見「絕對絕望少女 槍彈辯駁Another Episode」。 弹丸论破 希望學園與絕望高中生 ダンガンロンパ 希望の学園と絶望の高校生 Danganronpa: Trigger Happy Havoc 假名 だんがんろんぱ きぼうのがくえんとぜつぼうのこうこうせい 罗马字 Dangan-Ronpa: Kibō no Gakuen to Zetsubō no Kōkōsei 類型 高速推理動作遊戲&...

 

Qutb Shahi architecture

Indo-Islamic architectural style Qutb Shahi architecture is the distinct style of Indo-Islamic architecture developed during the reign of the Qutb Shahi dynasty, also known as the Golconda Sultanate. Qutb Shahi buildings are seen in the city of Hyderabad and its surroundings. The Golconda Fort, which predates the founding of the city is the earliest example. The style reached its zenith during the reign of Muhammad Quli Qutb Shah, who founded the city of Hyderabad and constructed the Charmina...

 

بابوا غينيا الجديدة

  بابوا غينيا الجديدة (بالإنجليزية: Papua New Guinea)‏  بابوا غينيا الجديدةعلم بابوا غينيا الجديدة بابوا غينيا الجديدةشعار بابوا غينيا الجديدة    الشعار الوطني(بالإنجليزية: A million different journeys)‏  النشيد: الأرض والسكان إحداثيات 6°18′S 147°00′E / 6.3°S 147°E / -6.3; 147  ...

Diagnosis of multiple sclerosis

This article needs additional citations for verification. Please help improve this article by adding citations to reliable sources. Unsourced material may be challenged and removed.Find sources: Diagnosis of multiple sclerosis – news · newspapers · books · scholar · JSTOR (March 2024) (Learn how and when to remove this message) Diagnosis of multiple sclerosisAnimation showing dissemination of brain lesions in time and space as demonstrated by monthly ...

 

Superligaen 2012/13

Superligaen Land Denemarken Bond DBU Competitie Superligaen Seizoensdetails Seizoen 2012/13 Kampioen FC Kopenhagen (10e titel) Topscorer(s) Andreas Cornelius (18 goals) Aantal clubs 12 Degradatie naar 1. Division Gedegradeerd Silkeborg IF, AC Horsens Europese kwalificatie FC Kopenhagen (CL), FC Nordsjælland (CL), Randers FC (EL), Esbjerg fB (EL) Algemeen Opgericht 1991 Recordtitelhouder FC Kopenhagen (10x) Website Superliga.dk Actueel Superligaen 2015/16 Navigatie Vorige   &#...

 

شويا (روسيا)

  لمعانٍ أخرى، طالع شويا (توضيح). شويا    علم شعار الإحداثيات 56°51′00″N 41°22′00″E / 56.85°N 41.366666666667°E / 56.85; 41.366666666667   تاريخ التأسيس 1539  تقسيم إداري  البلد روسيا[1][2]  خصائص جغرافية  المساحة 33 كيلومتر مربع  ارتفاع 100 متر  عدد السكان &#...

سابينا هيدالقو

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

 

Oldenburg in Holstein

Not to be confused with Oldenburg (city). You can help expand this article with text translated from the corresponding article in German. Click [show] for important translation instructions. Machine translation, like DeepL or Google Translate, is a useful starting point for translations, but translators must revise errors as necessary and confirm that the translation is accurate, rather than simply copy-pasting machine-translated text into the English Wikipedia. Do not translate text that app...

 

Ignacio Miramón

Ignacio MiramónNazionalità Argentina Altezza179 cm Calcio RuoloCentrocampista SquadraBoca Juniors CarrieraGiovanili Balonpié de Bolívar2019-2020 Gimnasia (LP) Squadre di club1 2020-2023 Gimnasia (LP)22 (0)2023-2024 Lille2 (0)2024-→  Boca Juniors0 (0) Nazionale 2023 Argentina U-204 (0) 1 I due numeri indicano le presenze e le reti segnate, per le sole partite di campionato.Il simbolo → indica un trasferimento in prestito. Statistiche aggiornate al 26 Luglio...

Inoue Kaoru

Japanese politician (1836–1915) MarquessInoue Kaoru 井上 馨GCMGMarquis Inoue KaoruMinister for Foreign AffairsIn office22 December 1885 – 17 September 1887Preceded bynoneSucceeded byItō HirobumiMinister of Agriculture and CommerceIn office25 July 1888 – 23 December 1889Preceded byKuroda KiyotakaSucceeded byIwamura MichitoshiMinister of Home AffairsIn office8 August 1892 – 15 October 1894Preceded byKōno TogamaSucceeded byNomura YasushiMinister of Finance...

 

جواز سفر صحراوي

جواز سفر صحراويالغلاف الأمامي للجواز السفر الصحراويمعلومات عامةنوع المستند جواز سفرالبلد الجمهورية العربية الصحراوية الديمقراطيةالغرض التعريف (هوية شخصية)صادر عن  الجمهورية العربية الصحراوية الديمقراطيةمتطلبات الاستحقاق الجنسية الصحراويةتعديل - تعديل مصدري - تعدي�...