Nedbrytning av örat - Ear decomposition

Ett exempel på en öronsönderdelning av en graf som innehåller 3 öron.

I grafteori , en öra av en oriktad graf G är en bana P där de två ändpunkterna av banan kan sammanfalla, men där annars ingen upprepning av kanter eller hörn är tillåten, så varje inre hörn i P har graden två i G . En sönderdelning av örat av en oriktad graf G är en partition av dess uppsättning kanter i en öronsekvens, så att de ena eller två ändpunkterna för varje öra tillhör tidigare öron i sekvensen och så att de inre hörnen i varje öra inte tillhör något tidigare öra. Dessutom måste det första örat i sekvensen i de flesta fall vara en cykel. En öppen sönderdelning eller en ordentlig sönderdelning av örat är en sönderdelning av örat där de två slutpunkterna för varje öra efter det första skiljer sig från varandra.

Öronnedbrytningar kan användas för att karakterisera flera viktiga grafklasser och som en del av effektiva grafalgoritmer . De kan också generaliseras från diagram till matroider .

Karaktäriserande diagramklasser

Flera viktiga klasser av grafer kan karakteriseras som att graferna har vissa typer av sönderdelning av örat.

Grafanslutning

En graf är k- vertikal-ansluten om avlägsnandet av några ( k  - 1) hörn lämnar en ansluten subgraf och k- kanten ansluten om borttagningen av några ( k  - 1) kanter lämnar en ansluten subgraf.

Följande resultat beror på Hassler Whitney  ( 1932 ):

En graf med är 2-vertex-ansluten om och endast om den har en öppen nedbrytning.${\ displaystyle G = (V, E)}$${\ displaystyle | E | \ geq 2}$

Följande resultat beror på Herbert Robbins  ( 1939 ):

En graf är 2-kantsansluten om och endast om den har en sönderdelning i örat.

I båda fallen är antalet öron nödvändigtvis lika med kretsrankningen för den angivna grafen. Robbins introducerade öronsönderdelningen av 2-kantsanslutna grafer som ett verktyg för att bevisa Robbins teorem , att detta är exakt de grafer som kan ges en starkt ansluten orientering. På grund av Whitneys och Robbins banbrytande arbete med nedbrytning av öron kallas en öronsönderfall ibland också en Whitney – Robbins-syntes ( Gross & Yellen 2006 ).

En icke-separerande öronsönderdelning är en öppen sönderdelning så att, för varje toppunkt v med endast ett undantag, har v en granne vars första uppträdande i nedbrytningen är i ett senare öra än det första utseendet på v . Denna typ av sönderdelning av örat kan användas för att generalisera Whitneys resultat:

En graf med är 3-vertex-ansluten om och endast om G har en icke-separerande öronsönderfall.${\ displaystyle G = (V, E)}$${\ displaystyle | V | \ geq 2}$

Om en sådan sönderdelning existerar kan den väljas med avseende på en viss kant uv av G på ett sådant sätt att u är i det första örat, v är det nya toppunktet i det sista örat med mer än en kant, och uv är en enkantigt öra. Detta resultat uttalades först uttryckligen av Cheriyan & Maheshwari (1988) , men som Schmidt (2013b) beskriver motsvarar det ett resultat i Ph.D. avhandling om Lee Mondshein. Strukturer nära besläktade med icke-separerande öronsönderfall av maximala plana grafer, kallade kanoniska ordningar, är också ett standardverktyg för grafritning .

Stark anslutning av riktade grafer

Ovanstående definitioner kan också tillämpas på riktade grafer . Ett öra skulle då vara en riktad bana där alla inre vertikaler har indegree och outdegree lika med 1. En riktad graf är starkt kopplad om den innehåller en riktad bana från varje toppunkt till varje annat toppunkt. Sedan har vi följande sats ( Bang-Jensen & Gutin 2007 , sats 7.2.2):

En riktad graf är starkt ansluten om och endast om den har en sönderdelning i örat.

Faktorkritiska grafer

En öronsönderdelning är udda om vart och ett av dess öron använder ett udda antal kanter. En faktorkritisk graf är en graf med ett udda antal hörn, så att för varje hörn v , om v tas bort från diagrammet, har de återstående hörnen en perfekt matchning . László Lovász  ( 1972 ) fann att:

En graf G är faktorkritisk om och endast om G har en udda sönderdelning av örat.

Mer allmänt gör ett resultat av Frank (1993) det möjligt att i någon graf G hitta öronsönderdelningen med minst jämna öron.

Serie – parallella grafer

Ett träd öra sönderdelning är en ordentlig örat sönderdelning i vilken den första örat är en enda kant och därefter varje öra , det finns en enda öra , så att båda ändpunkter ligger på ( Khuller 1989 ). En kapslad sönderdelning av örat är en sönderdelning av ett trädörat så att uppsättningen par av slutpunkter för andra öron som ligger inom varje öra bildar en uppsättning kapslade intervall. En serie – parallell graf är en graf med två angivna terminaler s och t som kan bildas rekursivt genom att kombinera mindre serie – parallella grafer på ett av två sätt: seriekomposition (identifierar en terminal från en mindre graf med en terminal från den andra mindre och hålla de andra två terminalerna som terminalerna för den kombinerade grafen) och parallell sammansättning (identifierar båda paren av terminaler från de två mindre graferna). ${\ displaystyle P_ {i}}$${\ displaystyle P_ {j}}$${\ displaystyle i> j}$${\ displaystyle P_ {i}}$${\ displaystyle P_ {j}}$${\ displaystyle P_ {j}}$${\ displaystyle P_ {i}}$${\ displaystyle P_ {j}}$

Följande resultat beror på David Eppstein  ( 1992 ):

En 2-vertex-ansluten graf är serie – parallell om och endast om den har en kapslad sönderdelning av örat.

Dessutom måste varje sönderdelning av öra öron i en 2-vertex-ansluten serie – parallell graf vara kapslad. Resultatet kan utvidgas till serie-parallella grafer som inte är 2-vertex-anslutna genom att använda öra sönderfall som börjar med en väg mellan de två terminalerna.

Matroider

Begreppet öronsönderfall kan utvidgas från diagram till matroider . En öronsönderdelning av en matroid definieras som en sekvens av kretsar av matroid, med två egenskaper:

• varje krets i sekvensen har en icke-snabb korsning med de tidigare kretsarna, och
• varje krets i sekvensen förblir en krets även om alla tidigare kretsar i sekvensen är kontrakterade.

När den tillämpas på den grafiska matroiden i ett diagram G sammanfaller denna definition av öronsönderfallning med definitionen av en korrekt öronsönderdelning av G : felaktiga nedbrytningar undantas av kravet att varje krets innehåller minst en kant som också tillhör tidigare kretsar . Med hjälp av denna definition kan en matroid definieras som faktorkritisk när den har en sönderdelning av örat där varje krets i sekvensen har ett udda antal nya element ( Szegedy & Szegedy 2006 ).

Algoritmer

På klassiska datorer kan sönderdelning av öron av 2-kantsanslutna grafer och öppna öronsönderfall av 2-vertex-anslutna grafer hittas av giriga algoritmer som hittar varje öra i taget. Ett enkelt girigt tillvägagångssätt som samtidigt beräknar sönderdelning av öron, sönderdelning av öra öron, st-numreringar och -orienteringar i linjär tid (om det finns) ges i Schmidt (2013a) . Tillvägagångssättet är baserat på att beräkna en speciell öronsönderdelning med namnet kedjesönderfall genom en väggenererande regel. Schmidt (2013b) visar att icke-separerande öronsönderfall också kan konstrueras i linjär tid.

Lovász (1985) , Maon, Schieber & Vishkin (1986) och Miller & Ramachandran (1986) tillhandahöll effektiva parallella algoritmer för att konstruera öronsönderfall av olika slag. Till exempel, för att hitta en sönderdelning av örat av en 2-kantsansluten graf, fortsätter algoritmen för Maon, Schieber & Vishkin (1986) enligt följande steg:

1. Hitta ett spännande träd i den angivna grafen och välj en rot för trädet.
2. Bestäm, för varje kant uv som inte är en del av trädet, avståndet mellan roten och den lägsta gemensamma förfadern till u och v .
3. För varje kant uv som är en del av trädet, hitta motsvarande "master edge", en icke- trädkant wx så att cykeln som bildas genom att lägga till wx till trädet passerar genom uv och sådan att w och x bland sådana kanter har en lägsta gemensamma förfader som är så nära roten som möjligt (med band som bryts av kantidentifierare).
4. Forma ett öra för varje icke-trädkant, bestående av den och de trädkanter som den är mästaren för, och beställ öronen efter deras huvudkantavstånd från roten (med samma slipsbrytande regel).

Dessa algoritmer kan användas som underrutiner för andra problem, inklusive testning av anslutningsmöjligheter, igenkänning av serie – parallella grafer och konstruktion av st- numreringar av grafer (en viktig delrutin vid planaritetstestning ).

En sönderdelning av öron av en viss matroid, med den ytterligare begränsningen att varje öra innehåller samma fasta element i matroiden, kan hittas i polynomisk tid med tillgång till ett självständighetsorakel för matroiden ( Coullard & Hellerstein 1996 ).

Referenser