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.

Grafteori

Innlegg Markus » 26/12-2017 01:26

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?
Markus offline
Fermat
Fermat
Innlegg: 760
Registrert: 20/09-2016 12:48
Bosted: NTNU

Re: Grafteori

Innlegg Gjest » 26/12-2017 11:50

Euler's characteristic formula
https://youtu.be/VvCytJvd4H0?t=599
Gjest offline

Re: Grafteori

Innlegg Gustav » 26/12-2017 15:40

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)
Gustav offline
Tyrann
Tyrann
Brukerens avatar
Innlegg: 4302
Registrert: 12/12-2008 12:44

Re: Grafteori

Innlegg Markus » 26/12-2017 21:28

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.
Markus offline
Fermat
Fermat
Innlegg: 760
Registrert: 20/09-2016 12:48
Bosted: NTNU

Re: Grafteori

Innlegg Aleks855 » 26/12-2017 22:25

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
Aleks855 offline
Rasch
Rasch
Innlegg: 5931
Registrert: 19/03-2011 15:19
Bosted: Trondheim

Re: Grafteori

Innlegg Markus » 27/12-2017 00:28

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$
Markus offline
Fermat
Fermat
Innlegg: 760
Registrert: 20/09-2016 12:48
Bosted: NTNU

Re: Grafteori

Innlegg Nebuchadnezzar » 27/12-2017 00:54

@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
Nebuchadnezzar offline
Fibonacci
Fibonacci
Brukerens avatar
Innlegg: 5540
Registrert: 24/05-2009 13:16
Bosted: NTNU

Re: Grafteori

Innlegg Markus » 27/12-2017 01:11

Nebuchadnezzar skrev:@Markus, sett nyeste videoen til 3Blue1Brown eller? ;)


Mulig det ja ;)
Markus offline
Fermat
Fermat
Innlegg: 760
Registrert: 20/09-2016 12:48
Bosted: NTNU

Re: Grafteori

Innlegg Gustav » 27/12-2017 02:18

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.
Gustav offline
Tyrann
Tyrann
Brukerens avatar
Innlegg: 4302
Registrert: 12/12-2008 12:44

Re: Grafteori

Innlegg Markus » 27/12-2017 12:02

Meget bra!
Markus offline
Fermat
Fermat
Innlegg: 760
Registrert: 20/09-2016 12:48
Bosted: NTNU

Hvem er i forumet

Brukere som leser i dette forumet: Ingen registrerte brukere og 6 gjester