En bro er en kant i grafteorien , hvis fjernelse øger antallet af forbundne komponenter [1] . Sådanne ribben er også kendt som skærende ribben , skærende buer eller landtange . En tilsvarende definition er, at en kant er en bro, hvis og kun hvis den ikke er indeholdt i nogen cyklus .
En graf med toppunkter kan højst indeholde broer, da tilføjelse af en kant mere uundgåeligt vil føre til udseendet af en cyklus. Grafer, der har præcis broer, er kendt som træer , og grafer, hvor enhver kant er en bro, er skove .
I enhver urettet graf er der en toppunktsækvivalensrelation , ifølge hvilken to toppunkter er ækvivalente , hvis der er to veje, der forbinder dem, som ikke skærer hinanden langs kanterne (enhver toppunkt betragtes som ækvivalent med sig selv). Ækvivalensklasserne af denne relation kaldes 2-kant-forbundne komponenter , og broerne i en graf er præcis de kanter, hvis ender tilhører forskellige komponenter. En grafs broblokdiagram har et toppunkt for enhver ikke-triviel komponent og en kant for hver bro [2] .
Broer er tæt beslægtet med begrebet hængsler , knudepunkter, der går ind i enhver sti, der forbinder nogle to knudepunkter. De to endespidser på en bro er hængslede, medmindre de er af grad 1, selvom ikke-brokanter også kan være hængslet i begge ender. Ligesom grafer uden broer, som er 2-kant-forbundne, er grafer uden hængsler vertex-2-forbundne .
I kubiske grafer er ethvert hængsel et endepunkt på mindst én bro.
Som navnet antyder, er en broløs graf en graf, der ikke har nogen broer. Tilsvarende betingelser er, at hver forbundne komponent i en graf har en åben ørenedbrydning [3] , at hver forbundne komponent er 2-kant-forbundet, eller (ved Robbins' sætning ) at hver forbundne komponent har en stærk orientering [3 ] .
Et vigtigt åbent problem relateret til broer er den dobbelte cyklusdækningsformodning , foreslået af Seymour og Székeres (i 1978 og 1979, uafhængigt), som siger, at enhver broløs graf kan dækkes af simple cyklusser, der indeholder hver kant to gange [4] .
Den første algoritme til at finde broer i en graf med lineær køretid blev beskrevet af Robert Tarjan i 1974 [5] . Algoritmen fungerer således:
Vi vil betegne kanten (v,w) indeholdt i træet som , og ikke indeholdt som .
.
Hvis det er en bro, så er det klart, at fra et undertræ, der er rodfæstet, burde der ikke være nogen måde at gå til et vertex, der ikke tilhører dette undertræ. For at tjekke dette er det nok at tjekke L(w), H(w) - betingelsen betyder, at vi ikke vil gå til det toppunkt, der ligger tættere på roden, og betingelsen betyder, at vi ikke går til et andet undertræ.
En meget simpel brosøgningsalgoritme [6] er baseret på kædenedbrydning. Kædenedbrydning giver ikke kun alle broer, den giver også alle hængsler (og dobbeltforbundne komponenter) af grafen G , hvilket giver et grundlag for test af kant- og toppunkt 2-forbindelse (og denne metode kan udvides til lineær-i-tid-verifikation af kant- og toppunkt 3-forbindelse).
Kædedekomponering er et særligt tilfælde af ørenedbrydning baseret på dybde-først søgning på træet T i graf G og kan gøres meget enkelt:
lad alle hjørner markeres som ubesøgte. For alle toppunkter v i stigende rækkefølge af gennemløbstal 1... n krydser vi hver bagudgående kant (det vil sige en kant, der ikke hører til krydsningstræet), der falder ind på v , og følger træets kanter til roden, indtil vi støde på det besøgte toppunkt. Under dette pas markerer vi alle passerede toppunkter som besøgte. Dette pas vil ende med enten en sti eller en løkke, der starter ved v , vi kalder dette en sti eller løkke en kæde . Vi vil betegne den i -te streng opnået ved en sådan procedure som C i . C=C 1 , C 2 ,... er da en opdeling af grafen G i kæder .
Følgende egenskaber gør det muligt at opnå nogle oplysninger om grafen G fra C effektivt, inklusive alle broer [6] :
Lad C være en kædenedbrydning af en simpel forbundet graf G=(V,E) .