3 hus på en rad skal motta vann, strøm og mat fra 3 stasjoner fra rekka nedenfor. Den ene stasjonen sender mat, den andre strøm og den siste vann. Alt dette sendes via respektive kabler til husene, slik at det i alt er 9 kabler. Gitt at bakken mellom de to rekkene er flat og at alle kablene må gå langs bakken (de kan ikke graves ned og opp igjen f.eks), er det mulig å legge opp kablene slik at ingen krysser hverandre?
Litt mer matematisk sagt; i en planar graf med $6$ noder, slik at den ser sånn ut:
$\begin{matrix}
A &B &C \\
& & \\
D& E &F
\end{matrix}$
Er det mulig å koble sammen A med F, E og D, B med F, E og D, samt C med F,E, og D uten at noen av kantene overlapper?
Grafteori
Moderators: Vektormannen, espen180, Aleks855, Solar Plexsus, Gustav, Nebuchadnezzar, Janhaa
Alternativt følger det direkte fra Wagners teorem: En endelig graf er planar hvis og bare hvis den ikke inneholder $K_{3,3}$ eller $K_5$ som en "minor" (usikker på det norske ordet for dette). ($K_{3,3}$ er nettopp den grafen vi betrakter, og en graf er alltid sin egen minor.)
(Det følger også av Kuratowskis teorem)
(Det følger også av Kuratowskis teorem)
Det er korrekt at det ikke er mulig å oppnå en slik modifikasjon, hvilket jeg tror du argumenterer for Gustav (så ikke et ja eller nei noe sted 
)
Og det er forsåvidt også korrekt at man også kan bruke Euler-karakteristikken for polyedere, slik som gjest påpeker, uten å gi noe argumentasjon for det.
)Og det er forsåvidt også korrekt at man også kan bruke Euler-karakteristikken for polyedere, slik som gjest påpeker, uten å gi noe argumentasjon for det.
Hvis jeg har forstått det riktig, så kan det argumenteres for at den minste syklusen som kan oppstå er en 4-syklus (to hus, to stasjoner), og hver av disse syklene vil avgrense en region. Siden det må finnes 5 (?) slike regioner, trenger vi 10 kanter (siden hver kant berører 2 regioner), men vi har bare 9.
Jeg tror argumentet ditt skal fungere, men ville venta på Gustav, for en proofread av en som faktisk kan dette godt.
For øvrig vil antall avgrensete regioner være $5$ slik du sier. Antall kanter og noder i grafen er konstant $9$ og $6$ respektivt, slik at du alltid kan være sikker på at det vil finnes $5$ avgrensete regioner av Euler-karakteristikken for et polyeder: $V - E + F = 2 \Longrightarrow F = 2 - 6 + 9 = 5$
For øvrig vil antall avgrensete regioner være $5$ slik du sier. Antall kanter og noder i grafen er konstant $9$ og $6$ respektivt, slik at du alltid kan være sikker på at det vil finnes $5$ avgrensete regioner av Euler-karakteristikken for et polyeder: $V - E + F = 2 \Longrightarrow F = 2 - 6 + 9 = 5$
-
Nebuchadnezzar
- Fibonacci
- Posts: 5648
- Joined: 24/05-2009 14:16
- Location: NTNU
@Markus, sett nyeste videoen til 3Blue1Brown eller?
"Å vite hva man ikke vet er og en slags allvitenhet" - Piet Hein
https://s.ntnu.no/Integralkokeboken
Lektor - Matematikk, Fysikk og Informatikk
https://s.ntnu.no/Integralkokeboken
Lektor - Matematikk, Fysikk og Informatikk
Jeg så også videoen, men i mitt hode er forklaringen hans bare forvirrende. Jeg ville formulert beviset slik: (bevis ved motsigelse)
Anta at grafen er planar. Hver region (F er antall regioner) er avgrenset av en sykel. Siden alle sykler består av minst 4 kanter, og hver kant hører til 2 regioner, må antall kanter være minst $\frac{4F}{2}$ (der 2 i nevneren kompenserer for overtelling), dvs. at $F\leq \frac12 E$, så Eulerkarakteristikken gir at $2=V-E+F\leq V-\frac12 E=\frac32$, som er motsigelsen. Ergo er grafen ikke planar.
Anta at grafen er planar. Hver region (F er antall regioner) er avgrenset av en sykel. Siden alle sykler består av minst 4 kanter, og hver kant hører til 2 regioner, må antall kanter være minst $\frac{4F}{2}$ (der 2 i nevneren kompenserer for overtelling), dvs. at $F\leq \frac12 E$, så Eulerkarakteristikken gir at $2=V-E+F\leq V-\frac12 E=\frac32$, som er motsigelsen. Ergo er grafen ikke planar.