Grafteori

Her kan brukere av forum utfordre hverandre med morsomme oppgaver og nøtter man ønsker å dele med andre. Dette er altså ikke et sted for desperate skrik om hjelp, de kan man poste i de andre forumene, men et sted for problemløsing på tvers av trinn og fag.

Moderatorer: Vektormannen, espen180, Aleks855, Solar Plexsus, Gustav, Nebuchadnezzar, Janhaa

Svar
Markus
Fermat
Fermat
Innlegg: 767
Registrert: 20/09-2016 13:48
Sted: NTNU

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?
Gustav
Tyrann
Tyrann
Innlegg: 4555
Registrert: 12/12-2008 12:44

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)
Markus
Fermat
Fermat
Innlegg: 767
Registrert: 20/09-2016 13:48
Sted: NTNU

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.
Aleks855
Rasch
Rasch
Innlegg: 6855
Registrert: 19/03-2011 15:19
Sted: Trondheim
Kontakt:

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.
Bilde
Markus
Fermat
Fermat
Innlegg: 767
Registrert: 20/09-2016 13:48
Sted: NTNU

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$
Nebuchadnezzar
Fibonacci
Fibonacci
Innlegg: 5648
Registrert: 24/05-2009 14:16
Sted: 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
Markus
Fermat
Fermat
Innlegg: 767
Registrert: 20/09-2016 13:48
Sted: NTNU

Nebuchadnezzar skrev:@Markus, sett nyeste videoen til 3Blue1Brown eller? ;)
Mulig det ja ;)
Gustav
Tyrann
Tyrann
Innlegg: 4555
Registrert: 12/12-2008 12:44

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.
Markus
Fermat
Fermat
Innlegg: 767
Registrert: 20/09-2016 13:48
Sted: NTNU

Meget bra!
Svar