Skillnad mellan versioner av "Jonahs stora seriösa sats"
Eric (diskussion | bidrag) (Utkast till bevis. Bör skrivas om för att bli överskådligare.) |
Eric (diskussion | bidrag) m |
||
| Rad 2: | Rad 2: | ||
Låt ''G'' vara en graf bestående av endast triangulära regioner. Då går det att ordna in samtliga regioner i par där varje region tillhör exakt ett par och de båda regionerna i ett par delar exakt en kant. | Låt ''G'' vara en graf bestående av endast triangulära regioner. Då går det att ordna in samtliga regioner i par där varje region tillhör exakt ett par och de båda regionerna i ett par delar exakt en kant. | ||
| + | |||
| + | == Originalformulering == | ||
| + | |||
| + | För en tre-dimensionell graf som uppfyller förutsättningarna ovan existerar det alltid ett eller flera sätt att quadifiera [sic] grafen. I andra termer: Det existerar alltid ett eller flera sätt att plocka ut par av trianglar som delar en kant och ta bort den kant de delar, så att <math>\displaystyle \deg r=4</math> för alla <math>r \in R</math>. | ||
| + | |||
| + | Denna sats är oerhört användbar när man konstruerar subdivideringsalgoritmer. | ||
== Bevis == | == Bevis == | ||
Versionen från 6 februari 2009 kl. 20.55
Satsen
Låt G vara en graf bestående av endast triangulära regioner. Då går det att ordna in samtliga regioner i par där varje region tillhör exakt ett par och de båda regionerna i ett par delar exakt en kant.
Originalformulering
För en tre-dimensionell graf som uppfyller förutsättningarna ovan existerar det alltid ett eller flera sätt att quadifiera [sic] grafen. I andra termer: Det existerar alltid ett eller flera sätt att plocka ut par av trianglar som delar en kant och ta bort den kant de delar, så att [math]\displaystyle \deg r=4[/math] för alla [math]r \in R[/math].
Denna sats är oerhört användbar när man konstruerar subdivideringsalgoritmer.
Bevis
Konstruera en ny graf H där varje region i G motsvaras av ett hörn, och förbind med kanter de punkter i H vars motsvarigheter i G delar en kant. Eftersom varje region i G gränsar till exakt 3 andra regioner gäller att varje hörn i H har grad 3. Vidare gäller att H saknar separerande kanter.
Välj nu en godtycklig delmängd X av hörnmängden i H. Betrakta antalet kanter som förbinder X med en godtycklig komponent med udda antal hörn av den inducerade delgrafen H\X. Antag att detta antal är 1. I så fall är denna kant separerande kant i grafen, och detta ger motsägelse. Antag att antalet är 2. Eftersom antalet hörn i H är jämnt (enligt Jonahs Lilla Seriösa Sats) gäller att komponenten består av två hörn med grad 2 och (eftersom |X| är udda) ett udda antal hörn med grad 3. Det innebär att summan av graderna för hörnen i komponenten är udda, vilket motsäger [math]\sum_{v \in V} \deg v = 2|E|[/math].
Nu har vi visat att antalet kanter som förbinder X med en komponent med udda antal hörn av H\X är minst tre. Antalet udda komponenter i H\X är mindre än |X|, eftersom alla hörn i H har grad 3. Nu tillämpar vi Tuttes sats och erhåller resultatet att det existerar en perfekt matchning i H. Därmed existerar en parning, som uppfyller villkoren, av regionerna i G, vilket skulle visas.
