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: 759
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)
Beware of the Ratmen during the full moon for they grow stronger as the moon gets fuller
Gustav offline
Tyrann
Tyrann
Brukerens avatar
Innlegg: 4276
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: 759
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: 5799
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: 759
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 og Fysikk
Nebuchadnezzar offline
Fibonacci
Fibonacci
Brukerens avatar
Innlegg: 5504
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: 759
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.
Beware of the Ratmen during the full moon for they grow stronger as the moon gets fuller
Gustav offline
Tyrann
Tyrann
Brukerens avatar
Innlegg: 4276
Registrert: 12/12-2008 12:44

Re: Grafteori

Innlegg Markus » 27/12-2017 12:02

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

Hvem er i forumet

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