Pfaffisk orientering

I grafteorin tilldelar en Pfaffisk orientering av en oriktad graf en riktning till varje kant, så att vissa cykler ("de jämna centrala cyklerna") har ett udda antal kanter i varje riktning. När en graf har en Pfaffian-orientering kan orienteringen användas för att räkna de perfekta matchningarna av grafen. Detta är huvudidén bakom FKT-algoritmen för att räkna perfekta matchningar i plana grafer , som alltid har Pfaffian-orientering. Mer generellt har varje graf som inte har verktygsgrafen $K_{3,3}$ som en grafmoll en Pfaffisk orientering, men $K_{3,3}$ inte, och inte heller oändligt många andra minimala icke-Pfaffiska grafer.

Definitioner

En Pfaffisk orientering av en oriktad graf är en orientering där varje jämn central cykel är konstigt orienterad. Termerna i denna definition har följande betydelser:

• En orientering är en tilldelning av en riktning till varje kant av grafen.
• En cykel $C$ är även om den innehåller ett jämnt antal kanter.
• En cykel $C$ är central om subgrafen för $G$ som bildas genom att ta bort alla hörn av $C$ har en perfekt matchning ; centrala cykler kallas också ibland alternerande kretsar.
• Cykel $C$ är konstigt orienterad om var och en av de två orienteringarna av $C$ överensstämmer med ett udda antal kanter i orienteringen.

Applikation för att räkna matchningar

Pfaffiska orienteringar har studerats i samband med FKT-algoritmen för att räkna antalet perfekta matchningar i en given graf. I denna algoritm används kanternas orienteringar för att tilldela värdena $\pm 1$ till variablerna i grafens Tutte-matris . Sedan ger Pfaffian för denna matris (kvadratroten av dess determinant ) antalet perfekta matchningar. Varje perfekt matchning bidrar med $\pm 1$ till Pfaffian oavsett vilken orientering som används; valet av en Pfaffisk inriktning säkerställer att alla dessa bidrag har samma tecken som varandra, så att ingen av dem avbryts. Detta resultat står i kontrast till den mycket högre beräkningskomplexiteten för att räkna matchningar i godtyckliga grafer.

Pfaffiska grafer

En graf sägs vara Pfaffian om den har en Pfaffian orientering. Varje plan graf är Pfaffian. En orientering där varje sida av en plan graf har ett udda antal medurs orienterade kanter är automatiskt Pfaffian. En sådan orientering kan hittas genom att börja med en godtycklig orientering av ett spännande träd i grafen. De återstående kanterna, inte i det här trädet, bildar ett spännande träd i den dubbla grafen , och deras orienteringar kan väljas enligt en nedifrån och upp genomgång av det dubbla spännträdet för att säkerställa att varje sida av den ursprungliga grafen har en udda antal medurs kanter.

Mer generellt har varje $K_{3,3}$ -mollfri graf en Pfaffisk orientering. Det här är graferna som inte har verktygsgrafen $K_{3,3}$ (som inte är Pfaffian) som en grafisk moll . Enligt Wagners teorem bildas K $K_{3,3}$ grafer genom att limma ihop kopior av plana grafer och hela grafen $K_{5}$ längs delade kanter . Samma limningsstruktur kan användas för att erhålla en Pfaffian-orientering för dessa grafer.

Tillsammans med $K_{3,3}$ finns det oändligt många minimala icke-Pfaffiska grafer. För tvådelade grafer är det möjligt att avgöra om en Pfaffisk orientering existerar, och i så fall hitta en, i polynomtid .