Öronnedbrytning

I grafteorin är örat på en oriktad graf G en väg P vars två ändpunkter kan sammanfalla, men annars är ingen upprepning av hörn eller kanter tillåten, så vilken som helst inre punkt av P har grad två i banan. En öronsönderdelning av en oriktad graf G är en uppdelning av dess kant i en sekvens av öron, så att ändpunkterna för varje öra tillhör tidigare valda öron i sekvensen, medan de inre hörnen av varje öra inte tillhör de föregående öron. I de flesta fall bör det första örat i sekvensen också vara en slinga. En öppen eller korrekt öronnedbrytning är en öronnedbrytning där de två ändpunkterna för varje öra förutom det första är olika.

Öronnedbrytning kan användas för att beskriva några viktiga klasser av grafer och som en del av effektiva grafalgoritmer . Öronnedbrytningen kan generaliseras till matroider .

Beskrivning av grafklasser

Vissa viktiga klasser av grafer kan beskrivas av vissa typer av öronnedbrytningar.

Grafanslutning

En graf är vertex-k-ansluten om du tar bort endast ( k  − 1) hörn lämnar subgrafen ansluten, och k-kant-ansluten om du tar bort några ( k  − 1) kanter lämnar subgrafen ansluten.

Följande resultat beror på Hasler Whitney [1] :

En graf med vertex är 2-kopplad om och bara om den har en öppen öronnedbrytning.

Följande resultat beror på Herbert Robinson [2] :

En graf är 2-kantskopplad om och bara om den har en öronnedbrytning.

I båda fallen måste antalet öron vara lika med kurvans konturrang . Robbins använde öronupplösning av 2-kants sammankopplade grafer som ett sätt att bevisa Robbins sats , att dessa är exakt grafer som kan ges en starkt sammankopplad orientering. Eftersom Whitney och Robinson var de första att utforska öronnedbrytning, kallas det ibland för Whitney–Robinson-syntesen [3] .

En icke- separerande öronsönderdelning är en öppen öronsönderdelning så att för varje vertex av v utom en har v en angränsande vertex som visas senare än v i sönderdelningen . Denna typ av nedbrytning kan användas för att generalisera Whitneys resultat:

En graf c är 3-vertex-ansluten om och endast om G har en icke-separerande öronnedbrytning.

Om en sådan sönderdelning existerar kan den väljas med avseende på en kant uv av G så att u tillhör det första örat, v är en ny vertex i sista örat med mer än en kant, och uv är ett öra som består av en kant. Detta resultat angavs först explicit av Cheryan och Maheshwari [4] , men, som Schmidt skriver [5] , är det likvärdigt med resultatet av Ph.D. 1971 avhandling av Lee Mondshein. Strukturer som är nära besläktade med icke-separerande öronnedbrytningar av maximala plana grafer, kallade kanoniska ordningar, är också en standardgrafvisualiserare .

Stark anslutning av riktade grafer

Definitionerna ovan kan även utvidgas till riktade grafer . Ett öra är då en riktad bana där alla inre hörn har indegree och outdegree lika med 1. En riktad graf är starkt sammankopplad om den innehåller en riktad bana från någon vertex till någon annan vertex. Då gäller följande sats:

En riktad graf är starkt kopplad om och bara om den har en öronnedbrytning.

På liknande sätt är en riktad graf dubbelt sammankopplad om det för två hörn finns en enkel cykel som innehåller båda hörnen. Sedan

En riktad graf är dubbelkopplad om och endast om den har en öppen öronnedbrytning.

Faktorkritiska grafer

En öronnedbrytning är udda om varje öra har ett udda antal kanter. En faktorkritisk graf är en graf med ett udda antal hörn, så att när någon vertex v tas bort från grafen har de återstående hörnen en perfekt matchning . Laszlo Lovas [6] fann att:

En graf G är en faktorkritisk graf om och endast om G har en udda öronsönderdelning.

Mer generellt gör Franks resultat [7] det möjligt att för vilken graf G som helst hitta en öronsönderdelning med minst antal jämna öron.

Parallellsekventiella grafer

En trädöra-nedbrytning är en riktig öronnedbrytning där det första örat är en enda kant och för varje efterföljande öra finns det ett unikt öra , , där båda ändpunkterna ligger på [8] . En sönderdelning av kapslade öron är en sönderdelning av trädöron så att, inom varje öra, uppsättningen av par av ändpunkter för andra öron som ligger inom , bildar en uppsättning kapslade intervall. En parallell-seriell graf är en graf med två distinkta ändar s och t , som kan formas rekursivt genom att kombinera mindre parallell-seriella grafer på ett av två sätt - seriell anslutning (vi identifierar ena änden av en av graferna med ena änden av den andra grafen, och den andra de två ändarna av båda graferna blir ändarna av föreningen) och en parallellkoppling (vi identifierar båda paren av terminaler av båda mindre grafer).

Följande resultat beror på David Epstein [9] :

En vertex-2-kopplad graf är en parallell-seriell graf om och endast om den har en kapslad öronnedbrytning.

Dessutom måste alla öppna öronnedbrytningar av en 2-vertex-kopplad parallell-seriegraf vara kapslad. Resultatet kan generaliseras till parallellsekventiella grafer som inte är 2-vertex-anslutna med hjälp av en öppen öronupplösning som utgår från en bana mellan de två ändarna.

Matroider

Begreppet öronnedbrytning kan generaliseras från grafer till matroider . En öronnedbrytning av en matroid definieras som en sekvens av matroidcykler som har två egenskaper:

När den tillämpas på en grafmatroid av en graf G , är denna definition av en öronnedbrytning densamma som definitionen av en korrekt nedbrytning av G — felaktiga nedbrytningar utesluts av kravet att varje cykel inkluderar minst en kant som tillhör till tidigare cykler. Med denna definition kan en matroid definieras som kvotkritisk om den har en öronnedbrytning där varje cykel i sekvensen har ett udda antal nya element [10] .

Algoritmer

Öronsönderdelning av 2-kants-anslutna grafer och öppen dekomposition av 2-vertex-anslutna grafer kan hittas med hjälp av giriga algoritmer som hittar varje öra en efter en. En enkel girig algoritm som beräknar öronexpansion, öppen öratexpansion, st-numrering och st-orientering i linjär tid (om de finns) på samma tid föreslogs av Schmidt [11] . Tillvägagångssättet är baserat på att beräkna en speciell typ av öronsönderdelning, kedjesönderdelning med en väggenereringsregel. Schmidt visade [5] att en icke-separerande öronnedbrytning kan byggas i linjär tid.

Lovas [12] , Maon, Shiber och Vyshkin [13] och Miller och Ramachandran [14] har tillhandahållit effektiva parallella algoritmer för att konstruera olika typer av öronnedbrytningar. Till exempel, för att hitta öronupplösningen av en 2-kants ansluten graf, går algoritmen för Maon, Schieber och Wyshkin [13] igenom följande steg:

  1. Spänningsträdet för den givna grafen hittas och roten till trädet väljs.
  2. För varje kant uv som inte är en del av trädet, bestäm avståndet mellan roten och den minst 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 kant wx som inte kommer från trädet, så att cykeln som bildas genom att lägga till wx till trädet går genom uv och så att bland alla kanter w och x har den lägsta förfadern så nära roten som möjligt.
  4. Vi bildar ett öra för varje icke-trädkant, bestående av denna kant och kanterna på trädet för vilken denna kant är den huvudsakliga. Vi arrangerar öronen enligt huvudkantens avstånd från roten.

Denna algoritm kan användas som en procedur för andra problem, inklusive kontroll av anslutning, igenkänning av seriell-parallella grafer och konstruering av en st -numrering av grafer (en viktig procedur för att kontrollera planaritet ).

En öronsönderdelning av en matroid, med den ytterligare begränsningen att varje öra innehåller samma fasta antal matroidelement, kan hittas i polynomtid om det finns ett oberoende orakel för matroiden [15] .

Anteckningar

  1. ↑ Whitney, 1932 .
  2. ↑ Robbins, 1939 .
  3. ↑ Gross, Yellen, 2006 .
  4. ↑ Cheriyan, Maheshwari, 1988 .
  5. ↑ 12 Schmidt, 2013b .
  6. ↑ Lovász, 1972 .
  7. ↑ Frank, 1993 .
  8. ↑ Huller, 1989 .
  9. ↑ Eppstein, 1992 .
  10. ↑ Szegedy, Szegedy, 2006 .
  11. ↑ Schmidt, 2013a .
  12. ↑ Lovász, 1985 .
  13. ↑ 1 2 Maon, Schieber, Vishkin, 1986 .
  14. ↑ Miller, Ramachandran, 1986 .
  15. ↑ Collard, Hellerstein, 1996 .

Litteratur