Bridge (grafteori) - Bridge (graph theory)
I grafteorin är en brygga , isthmus , skäregg eller skärbåge en kant på en graf vars radering ökar grafens antal anslutna komponenter . Likaså är en kant en bro om och bara om den inte ingår i någon cykel . För en ansluten graf kan en bro unikt bestämma ett snitt . En graf sägs vara brygglös eller isthmusfri om den inte innehåller några broar.
Denna typ av brygga bör särskiljas från en orelaterad betydelse av "bro" i grafteorin, en delgraf som skiljs från resten av diagrammet med en specificerad delmängd av hörn; se Ordlista över grafteoretiska termer § bro .
Träd och skogar
En graf med noder kan innehålla högst broar, eftersom att lägga till ytterligare kanter måste skapa en cykel. Diagrammen med exakt broar är exakt träden , och diagrammen där varje kant är en bro är exakt skogarna .
I varje oriktad graf finns det en ekvivalensrelation på hörnpunkterna enligt vilka två hörn är relaterade till varandra när det finns två kantseparerade banor som förbinder dem. (Varje toppunkt är relaterat till sig själv via två längd-noll-banor, vilka är identiska men ändå kantseparera.) Ekvivalensklasserna för denna relation kallas 2-kantanslutna komponenter , och broarna i diagrammet är exakt de kanter vars slutpunkter tillhör olika komponenter. Den bro-blockträd av grafen har en vertex för varje icke-triviala komponent och en kant för varje bro.
Förhållande till toppunktanslutning
Broar är nära besläktade med begreppet artikulationshörn , hörn som tillhör varje väg mellan några par andra hörn. De två ändpunkterna för en bro är artikulationshörn, såvida de inte har graden 1, även om det också kan vara möjligt för en icke-bryggkant att ha två artikulationshörn som slutpunkter. Analogt med brygglösa grafer som är 2-kantsanslutna, är grafer utan artikulationshörn 2-vertex-anslutna .
I ett kubiskt diagram är varje klipphörn en slutpunkt på minst en bro.
Bridgeless grafer
En brofri graf är en graf som inte har några broar. Motsvarande villkor är att varje ansluten komponent i diagrammet har en öppen sönderdelning av örat , att varje ansluten komponent är 2-kantsansluten , eller (av Robbins sats ) att varje ansluten komponent har en stark orientering .
Ett viktigt öppet problem som involverar broar är cykelns dubbeltäckningsgissningar på grund av Seymour och Szekeres (1978 och 1979, oberoende), som säger att varje brofri graf medger en flersats med enkla cykler som innehåller varje kant exakt två gånger.
Tarjans bro-hitta algoritm
Den första linjära tidsalgoritmen för att hitta broar i en graf beskrevs av Robert Tarjan 1974. Den utför följande steg:
- Hitta en spännande skog av
- Skapa en rotad skog från den spännande skogen
- Korsa skogen i förbeställning och numrera noderna. Föräldernoder i skogen har nu lägre antal än barnnoder.
- För varje nod i förbeställning (betecknar varje nod med dess förbeställningsnummer), gör:
- Beräkna antalet skogsavkomlingar för denna nod genom att lägga till en till summan av barnens ättlingar.
- Beräkna , den lägsta förbeställningsetiketten som kan nås genom en sökväg för vilken alla utom den sista kanten förblir inom det subtree som är rotat till . Detta är det minsta av uppsättningen som består av förbeställningsetiketten för , av värdena på undernoder och förförbeställningsetiketterna för noder som kan nås från kanter som inte hör till .
- Beräkna på samma sätt den högsta förbeställningsetiketten som kan nås genom en sökväg för vilken alla utom den sista kanten förblir inom det subtree som är rotat till . Detta är det maximala av uppsättningen som består av förbeställningsetiketten för , av värdena på undernoder och förförbeställningsetiketterna för noder som kan nås från kanter som inte hör till .
- För varje nod med överordnad nod , om och sedan kanten från till är en brygga.
Brofynd med kedjesönderfall
En mycket enkel bro-hitta-algoritm använder kedjesönderfall . Kedjanedbrytningar tillåter inte bara att beräkna alla broar i en graf, de tillåter också att avläsa varje klipphörn av G (och det blockklippta trädet av G ), vilket ger en allmän ram för testning av 2-kant- och 2-toppunkt -anslutning (som sträcker sig till linjära 3-kant- och 3-vertex-anslutningstest).
Kedjanedbrytningar är speciella öronnedbrytningar beroende på ett DFS-träd T av G och kan beräknas mycket enkelt: Låt varje toppunkt markeras som obesökt. För varje toppunkt v i stigande DFS- nummer 1 ... n , korsa varje bakkant (dvs. varje kant som inte finns i DFS-trädet) som inträffar v och följ vägen för trädkanterna tillbaka till roten till T , stanna vid det första toppunktet som är markerat som besökt. Under en sådan genomgång markeras varje genomkorsad topp som besökt. Således stannar en genomgång senast vid v och bildar antingen en riktad väg eller cykel, som börjar med v; vi kallar denna väg eller cyklar en kedja . Den i : te kedja hittas genom denna procedur hänvisas till som C i . C = C 1 , C 2 , ... är då en kedja sönderdelning av G .
Följande karakteriseringar tillåter sedan att avläsa flera egenskaper hos G från C effektivt, inklusive alla broar av G . Låt C vara en kedjesönderdelning av en enkel ansluten graf G = (V, E) .
- G är 2-kant-förbundna om och endast om kedjorna i C partition E .
- En kant e i G är en bro om och endast om e inte finns i varje kedja i C .
- Om G är ansluten med två kanter är C en öronsönderdelning .
- G är 2-vertex-anslutas om och endast om G har minimum två och C 1 är den enda cykeln i C .
- En vertex v i en 2-kantsansluten graf G är en cut-topp om och bara om v är det första toppunktet för en cykel i C - C 1 .
- Om G är 2-vertex-ansluten är C en öppen nedbrytning .
Brohuvud
För en ansluten graf kan en brygga separeras i region och region , dvs. klippningen . Hörnpunkterna och är de två brohuvudena på och . är nästan brohuvudet för och långt brohuvudet , och vice versa för .
