Side 1 av 1

Grafteori

Lagt inn: 26/12-2017 01:26
av Markus
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?

Re: Grafteori

Lagt inn: 26/12-2017 11:50
av Gjest
Euler's characteristic formula
https://youtu.be/VvCytJvd4H0?t=599

Re: Grafteori

Lagt inn: 26/12-2017 15:40
av Gustav
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)

Re: Grafteori

Lagt inn: 26/12-2017 21:28
av Markus
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.

Re: Grafteori

Lagt inn: 26/12-2017 22:25
av Aleks855
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.

Re: Grafteori

Lagt inn: 27/12-2017 00:28
av Markus
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$

Re: Grafteori

Lagt inn: 27/12-2017 00:54
av Nebuchadnezzar
@Markus, sett nyeste videoen til 3Blue1Brown eller? ;)

Re: Grafteori

Lagt inn: 27/12-2017 01:11
av Markus
Nebuchadnezzar skrev:@Markus, sett nyeste videoen til 3Blue1Brown eller? ;)
Mulig det ja ;)

Re: Grafteori

Lagt inn: 27/12-2017 02:18
av Gustav
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.

Re: Grafteori

Lagt inn: 27/12-2017 12:02
av Markus
Meget bra!