Skillnad mellan versioner av "Jonahs lilla seriösa sats"
Eric (diskussion | bidrag) |
Eric (diskussion | bidrag) |
||
| (3 mellanliggande versioner av samma användare visas inte) | |||
| Rad 15: | Rad 15: | ||
== Bevis == | == Bevis == | ||
| − | + | Vi avser här bevisa att samtliga av grafens komponenter har ett jämnt antal regioner. Då gäller också att hela grafen har ett jämnt antal regioner. Välj därför en av grafens komponenter. | |
| − | Välj en region och ta bort den. Veckla ut grafen och lägg den i planet. Den borttagna regionen har nu identifierats med den oändliga region som ligger utanför | + | Välj en region och ta bort den. Veckla ut grafen och lägg den i planet. Den borttagna regionen har nu identifierats med den oändliga region som ligger i planet, utanför grafen. Låt <math>\displaystyle R</math> och <math>\displaystyle E</math> vara mängden av regioner respektive kanter i den nya grafen. Givet i förutsättningarna är att varje region gränsar till exakt tre andra regioner, alltså att varje region har tre kanter. Därför gäller |
<math>\sum_{r \in R} \deg r = 3|R|</math> | <math>\sum_{r \in R} \deg r = 3|R|</math> | ||
| − | Varje kant gränsar till exakt två regioner. Därmed gäller även | + | Varje kant gränsar till exakt två regioner. Detta innebär att summerar vi <math>\displaystyle \deg r</math> för alla <math>r \in R</math> har vi räknat varje kant två gånger. Därmed gäller även |
<math>\sum_{r \in R} \deg r = 2|E|</math>. | <math>\sum_{r \in R} \deg r = 2|E|</math>. | ||
| Rad 31: | Rad 31: | ||
Alltså är antalet regioner ett jämnt tal, vilket skulle visas. | Alltså är antalet regioner ett jämnt tal, vilket skulle visas. | ||
| + | |||
| + | == Jonahs Otriviala Följdsats == | ||
| + | |||
| + | 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. | ||
[[Kategori:Satser]] | [[Kategori:Satser]] | ||
Versionen från 10 januari 2009 kl. 20.16
Jonahs Seriösa Sats är den enda seriösa satsen skapad av Jonah. Den bevisades nyss.
Definitioner
- En tre-dimensionell graf är en punkt-, kant- och regionmängd där varje punkt är en ordnad mängd av tre tal, varje kant är en oordnat mängd av två punkter i grafen och varje region är en kantcykel.
- En "stängd" tre-dimensionell graf är en tre-dimensionell graf sådan att det inte existerar någon väg över regionerna som gör att man når andra sidan av en region.
- En triangulär region är en kantcykel av längd exakt 3.
Satsen
Låt G vara en stängd tre-dimensionell graf med endast triangulära regioner. (Om grafen har andra regioner måste dessa subdivideras först). Jonahs Seriösa sats säger då att antalet regioner i G alltid är jämnt.
Bevis
Vi avser här bevisa att samtliga av grafens komponenter har ett jämnt antal regioner. Då gäller också att hela grafen har ett jämnt antal regioner. Välj därför en av grafens komponenter.
Välj en region och ta bort den. Veckla ut grafen och lägg den i planet. Den borttagna regionen har nu identifierats med den oändliga region som ligger i planet, utanför grafen. Låt [math]\displaystyle R[/math] och [math]\displaystyle E[/math] vara mängden av regioner respektive kanter i den nya grafen. Givet i förutsättningarna är att varje region gränsar till exakt tre andra regioner, alltså att varje region har tre kanter. Därför gäller
[math]\sum_{r \in R} \deg r = 3|R|[/math]
Varje kant gränsar till exakt två regioner. Detta innebär att summerar vi [math]\displaystyle \deg r[/math] för alla [math]r \in R[/math] har vi räknat varje kant två gånger. Därmed gäller även
[math]\sum_{r \in R} \deg r = 2|E|[/math].
Vi har nu visat att
[math]\displaystyle 3|R| = 2|E|[/math]
Alltså är antalet regioner ett jämnt tal, vilket skulle visas.
Jonahs Otriviala Följdsats
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.
