De digitale vraagbaak voor het wiskundeonderwijs

home |  vandaag |  gisteren |  bijzonder |  gastenboek |  wie is wie? |  verhalen |  contact

HOME

samengevat
vragen bekijken
een vraag stellen
hulpjes
zoeken
FAQ
links
twitter
boeken
help

inloggen

colofon

  \require{AMSmath}

Grafen

Equivalentie aantonen van definities

Beste,

Een outerplanar graaf heeft twee definities. 1) Een graaf G is outerplanar als het een planaire tekening heeft waarbij all vertices op de ongebonden (externe) regio ligt. 2) Een graaf G is outerplanar als je een vertex kan tekenen in de ongebonden regio, en die met lijnen verbindt met alle vertices in G, zodanig dat deze nieuwe graaf nog steeds planair is.

Het lukt mij niet om te bewijzen dat 1 impliceert 2, en dat 2 impliceert 1. Met een tekening lukt het maar dat is geen bewijs. Hulp is gewenst.

Marco
2-3-2022

Antwoord

Printen
Dit is niet geheel flauw. Bij het werk aan planaire grafen wordt gebruik gemaakt van de Curvenstelling van Jordan; het bewijs hiervan is niet triviaal.

Met behulp hiervan kun je inzien dat de rand van de onbegrensde component van het complement uit de punten en een deel van de lijnen uit de graaf bestaat en dat je met de klok meet over een grote cirkel je graaf kunt lopen en dan aan je rechterhand om en om een punt en een lijn ziet (het kan zijn dat je sommige lijnen en punten meer dan één keer ziet. Je kun dan telkens een kromme van de cirkel naar elk punt dat je ziet maken en zo dat die krommen elkaar niet snijden. Buiten de cirkel kun je die doortrekken naar één enkel punt en dat bewijst de ene implicatie (er zijn veel details in te vullen).

Het omgekeerde is makkelijker: als die uitgebreide graaf planair is teken hem dan zonder kruisende lijnen op een boloppervlak. De krommen vanuit het extra punt laten zien dat alle punten liggen op de rand van de component van het complement waar het extra punt in ligt. Laat uit die component één punt weg (dat niet op de graaf ligt. Wat je overhoudt van het boloppervlak is het platte vlak.

kphart
2-3-2022


De graad van een vertex in een outerplanar graaf

Gegeven is een outerplanar graaf. Te bewijzen is dat er een vertex bestaat in de graaf met graad hoogstens 2. Ik heb een bewijs gevonden dat een deel van de graaf bekijkt zonder kanten die volledig in een inner-regio liggen (inner face). Echter snap ik niet hoe we dan direct concluderen dat de graad van een vertex hoogstens 2 is.

Het bewijs:
Choose an arbitrary interior edge. Since it connects two points on the exterior of the graph, it divides the graph into two parts. Choose one of the parts. Pick an interior edge in that part. It divides the graph again. Pick the part that does not contain the first edge. Keep going in this way, always picking the part not containing your previously chosen edges. As there are only finitely many edges, eventually this has to stop - there are no more interior edges on one side of your final pick. But since faces with two edges only are not allowed, the face on that side has to have at least one more vertex. Any such vertex cannot have an interior edge connecting to it, so it can only have the two exterior edges. I.e., its degree is 2. (https://math.stackexchange.com/questions/2781157/two-questions-about-outerplanar-graph-while-working-on-a-3-color-problem-of-the)

Richar
4-3-2022

Antwoord

Printen
Het antwoord is onvolledig: de overgebleven graaf, inclusief die laatste lijn, heeft inderdaad geen `inner edges' meer maar hoeft niet uit een `face' te bestaan; er kunnen nog extra lijnen uit de punten vertrekken en er kunnen nog meer faces zijn.
Hier is een ander argument: neem aan dat je graaf samenhangend is (neem andere een component van je graaf) en niet flauw is, met tenminste vier punten.
Bij drie punten of minder heb je zeker een punt met graad $1$ of $2$.
Neem twee punten $u$ en $v$ met maximale afstand: het kortste pad tussen $u$ en $v$ is het langste van alle kortste paden tussen paren punten.
Bewering $u$ en $v$ hebben graad $2$.
Stel $u$ heeft drie of meer buren, zeg $w_1$, $w_2$, en $w_3$.
Het kortste pad $P_i$ van $w_i$ naar $v$ loopt niet door $u$ (want dan zou het $1$ langer zijn dan het kortste pad van $u$ naar $v$.
Zo krijgen we drie paden van $u$ naar $v$: telkens van $u$ naar $w_i$ en dan $P_i$ volgen. Die paden komen bij elkaar bij $v$ of eerder, misschien al meteen na de $w_i$. Teken een plaatje van zo'n situatie: er zal altijd een $i$ zijn zo dat $w_i$ binnen de cykel gevormd door de paden via de andere twee $w$s.
Maar dan zou $G$ niet outerplanair zijn: die $w_i$ is van buiten niet te zien.

kphart
5-3-2022


Re: De graad van een vertex in een outerplanar graaf

Bedankt voor uw antwoord. Prachtig bewijs. Stel dat er een lijn is van w1 naar w2, en een lijn van w2 naar w3. Stel nu dat het kortste pad van w1 naar v via w2 en dan w3 gaat. Stel nu ook dat het kortste pad van w2 naar v via w3 gaat. Stel verder dat het kortste pad van w3 naar v niet via de andere w’s gaat. Dan hebben we geen cykel waarin een w ‘opgesloten’ zit. Hoe lossen we dit randgeval op?

Richar
5-3-2022

Antwoord

Printen
Het geval dat het kortste pad van $w_1$ naar $v$ via $w_2$ en $w_3$ gaat doet zich niet voor: dan is dat kortste pad $1$ langer dan het het pad dat je krijgt door van $u$ naar $w_3$ te gaan en dat het pad vanuit $w_1$ te volgen.
Maar het zou toch mogelijk zijn dat de kortste paden vanuit $w_1$ en $w_3$ (ook) via $w_2$ lopen.

Daarom moeten we he bewijs toch iets aanpassen: volg het bewijs van mathoverflow tot we een graaf zonder inner edges hebben, en neem aan dat die samenhangend is. Bekijk de laatste inner edge, zeg $\{a,b\}$.
Neem vanuit elk ander punt het kortste pad naar $a$, en neem het punt $u$ waarvoor dit punt het langst is, en neem aan dat die drie buren $w_1$, $w_2$, en $w_3$ heeft.
Als nu, bijvoorbeeld, $w_2$ met $w_1$ en $w_3$ verbonden is dan is $\{u,w_2\}$ een inner edge binnen het cykel $\{u,w_1,w_2,w_3\}$, maar dat kan niet.
Er is dus ten hoogste één verbinding tussen de buren. Als die er niet is zijn we klaar, als in het vorige antwoord.
Als, bijvoorbeeld, $\{w_2,w_3\}$ een verbinding is en het kortste pad van beide naar $a$ loopt via $w_2$ dan loopt er geen ander pad van $w_3$ naar $a$, anders krijgen we dezelfde tegenspraak als in het vorige antwoord.
Dus als $v$ een andere buur van $w_3$ is loopt het kortste pad van $v$ naar $a$ via $w_3$, maar dan is het $1$ langer dan het kortste pad van $w_3$ naar $a$ en dus ook $1$ langer dan het kortste pad van $u$ naar $a$, tegenspraak. Conclusie: $w_3$ heeft alleen $u$ en $w_2$ als buren en heeft dus graad $2$.

kphart
6-3-2022


Minimale koppeling

Gegeven is een ongerichte graaf G met knopen V en kanten E, en een knopenbedekking X. Gevraagd is om een koppeling K te vinden van minimale kardinaliteit waarbij de eindpunten van de kanten in de koppeling een superset vormen van C. Bovendien moet K worden gevonden in polynomiale tijd in de grootte van de invoer.

Ik heb geprobeerd om hier een recursieve formule van te maken, waarbij ik alle deelverzamelingen van E bekijk. Namelijk, door voor elke knoop in C uit te proberen welke aangrenzende kant ik neem. Aangezien ik nog niet weet wat optimaal is, probeer ik alle aangrenzende kanten. Dit is echter exponentieel in E, aangezien ik alle deelverzamelingen van E moet bekijken. Er lijkt een veel eenvoudigere oplossing voor dit probleem aangezien een koppeling en bedekking erg gerelateerd zijn aan elkaar. Echter loop ik hierop vast. Hulp is gewenst.

Richar
25-3-2022

Antwoord

Printen
Zoals het nu geformuleerd is zal het niet lukken: een koppeling pakt een even aantal knopen. Als $C$ uit alle knopen bestaat, dus $C=V$, en als er een oneven aantal knopen is dan pakt de koppeling zeker niet alle knopen mee.

Er moeten dus voorwaarden bij: over de aard van de overdekking, over de aard van de graaf, ...

kphart
25-3-2022


Re: Minimale koppeling

Excuses, ik ben erbij vergeten te vermelden: als een dergelijke koppeling K onmogelijk is om te vinden (bijvoorbeeld omdat C bestaat uit geïsoleerde knopen), dan moeten we dat ook aangeven. Over de vorm van de gegeven graaf of aard van de gegeven knoppendekking mogen verder geen assumpties worden gemaakt.

Richar
25-3-2022

Antwoord

Printen
De ultieme methode ken ik niet maar je kunt dit soort problemen als een stromingsprobleem zien, bijvoorbeeld voor tweedelingsgrafen door van alle lijnen pijlen te maken die allemaal dezelfde kant op wijzen, en een bron en een put toe te voegen.

Een maximale stroom geeft je dan een maximum koppeling. Zie ook de Stelling van Konig-Egervary.

Je zou je probleem tot dit probleem kunnen proberen te reduceren door twee kopieën, $V\times\{0\}$ en $V\times\{1\}$, van $V$ naast elkaar te zetten en een pijl van $(v,0)$ naar $(w,1)$ te trekken als er een lijn van $v$ naar $w$ loopt.
Voro het vinden van maximale stromen zijn polynomiale algoritmen beschikbaar.

kphart
25-3-2022


klein |  normaal |  groot

home |  vandaag |  bijzonder |  gastenboek |  statistieken |  wie is wie? |  verhalen |  colofon

©2001-2022 WisFaq - versie 3