© h.hofstede (h.hofstede@hogeland.nl)

Bruggen.   (nee; niet die van Königsberg!)
       
Bruggen hebben (dat zal je niet verbazen) te maken met verbindingen. In grafen is dat ook zo.
 
"Een brug van een deelgraaf D bestaat uit een verzameling knooppunten die allemaal door paden met elkaar verbonden zijn, en waarvoor die paden nooit in D liggen. Alleen de begin- en eindpunten van die paden mogen punten van D zijn".
       
Hieronder zie je een graaf, met drie keer een deelgraaf D gekozen (de rode knooppunten). De eerste D heeft twee bruggen de tweede D heeft 3 bruggen en de laatste D heeft 1 brug. De bruggen zijn steeds groenig/blauwig getekend
       

       
Bedenk dat de knooppunten van D waar de brug aan vast zit óók bij de brug horen (die heb ik een groenige rand en een rode vulling gegeven).
Deze knooppunten die de brug dus gemeenschappelijk met D heeft, noem ik de aanknooppunten. Je ziet in de figuur dat een brug één of meerdere aanknooppunten met D kan hebben. De enige knooppunten die twee bruggen gemeenschappelijk hebben zijn hun eventuele aanknooppunten aan D.

We gaan die bruggen van D nu karakteriseren aan de hand van hun aanknooppunten.
   
Op de eerste plaats gaan we dat doen aan de hand van het aantal aanknooppunten: een brug met k aanknooppunten heet daarom vanaf nu een k-brug.  Twee k-bruggen met precies dezelfde aanknooppunten noemen we equivalent.
"Huh?  Zijn dat dan niet precies dezelfde bruggen?", hoor ik je al denken. In de graaf hiernaast zie je dat dat niet hoeft. Daar staan twee verschillende 3-bruggen van de rode deelgraaf met dezelfde aanknooppunten (bedenk dat die aanknooppunten alleen eind- en beginpunt van een pad mogen zijn, dus de bruggen lopen niet "door").

Vervolgens gaan we kijken naar de manier waarop de bruggen aan D vastzitten. Dat doen we eerst door voor D een eenvoudige vorm te kiezen:  een cykel.

       
De aanknopingspunten van een brug verdelen de cykel D in een aantal segmenten. Hiernaast zie je 4 aanknooppunten die D in 4 segmenten verdelen.

Voor de ligging van  de aanknooppunten van verschillende bruggen onderscheiden we nu de volgende gevallen:

1.  Twee bruggen vermijden elkaar als alle aanknooppunten van één van beiden binnen één segment van de andere liggen (de randpunten horen bij het segment). Als dat niet zo is dan overlappen de bruggen.

2.  Twee overlappende bruggen zijn verspringend als er langs de cykel vier verschillende aanknooppunten te vinden zijn die om-en-om bij de ene brug en de andere brug horen. (Voor een punt van beide bruggen mag je kiezen bij welke brug je hem telt)

Hieronder zie je wat voorbeelden van de verschillende gevallen.

       

       
Tenslotte nog een derde onderscheid. Een cykel is een Jordankromme, dus verdeelt het vlak in een binnengebied en een buitengebied. Een brug met alle knooppunten (behalve de aanknooppunten) in het binnengebied heet een binnenbrug, en eentje met  knooppunten in het buitengebied heet een buitenbrug. Hierboven zie je links twee binnenbruggen, in het midden en rechts een groene binnenbrug en een rode buitenbrug.

Oké, genoeg naamgeving, op naar de stellingen!   Vanaf hier voor planaire grafen!!

Hier volgen een aantal stellingen, uiteindelijk resulterend in de beroemde "stelling van Kuratowski".
       
Stelling 1:  Overlappende bruggen zijn   óf verspringend,  óf equivalente 3-bruggen

Dat kun je eigenlijk aan het middelste plaatje hierboven al wel zien:  zodra je één van de groene of rode punten verplaatst kun je vier verschillende om-en-om punten vinden, en zijn de bruggen verspringend.
Netter bewijs:

•

 Als één van  beide bruggen een 1-brug is, kunnen de bruggen niet overlappend zijn, want dat ene punt kan maar in één segment van de andere brug liggen. Dus beide bruggen zijn minstens 2-bruggen.

•

 Als één van de bruggen een 2-brug is, mogen die twee punten niet binnen één segment van de andere brug liggen. Dus tussen die twee punten ligt een punt van de andere brug. Dus zijn de bruggen verspringend.

•

Neem twee bruggen van 3 of hoger......
Als ze niet equivalent zijn dan is er ergens een punt p' van brug B' dat tussen twee opeenvolgende punten p en q van B in ligt (als ze niet opeenvolgend zijn kies je een andere p of q). Maar er moet minstens nog één ander punt van B' te vinden zijn dat niet op segment pq ligt (anders zouden de bruggen vermijdend zijn)
Dus zijn de bruggen verspringend.

Blijft over het geval, van equivalente bruggen van 3 of hoger. Bruggen van 4 of hoger zijn automatisch verspringend (laat de punten om-en-om bij brug B en brug B' meetellen)

  Dus het enige geval is inderdaad een equivalente 3-brug.
■      
       
Stelling 2:   Als een brug drie aanknooppunten k1, k2, k3 heeft, dan bestaat er binnen de punten van die brug een knooppunt k0  zodat de routes k1k0 en k2k0 en k3k0  alleen punt k0 gemeenschappelijk hebben.
     

Bekijk de route k1k2 daar moet minstens nog één ander punt k op liggen (anders kan k3 nooit bij de brug horen).

Bekijk nu de route k3k, en stel dat die voor het eerst in k0 een punt gemeenschappelijk met k1k2 heeft.

Dan hebben k1k0 en k2k0 en k3k0 geen punt gemeenschappelijk, dus k0 voldoet aan de voorwaarden.
('t is hiernaast getekend voor een binnenbrug, maar 't geldt natuurlijk precies zo voor een buitenbrug)
■      
       
Stelling 3.  Binnenbruggen vermijden elkaar  (buitenbruggen trouwens ook)
       
Stel dat twee binnenbruggen elkaar overlappen. Dan zijn er volgens stelling 1 twee mogelijkheden:  ze zijn óf verspringend, óf het zijn equivalente 3-bruggen. Laten we beide gevallen bekijken:
       
  1. Ze zijn verspringend.
Dan bestaan er in de cykel D dus vier punten  p - p' - q - q'   (de accentpunten van de ene brug, de niet-accentpunten van de andere).
Maar de routes  pq in de ene brug en p'q' in de andere brug kunnen geen gemeenschappelijk punt hebben, want dan waren het niet twee verschillende bruggen.

pq verdeelt de cykel in twee gebieden, en volgens de theorie van de Jordan krommen van de vorige les, kan  p'q' niet van het ene naar het andere gebied komen zonder pq te snijden

       
  2. Het zijn twee equivalente 3-bruggen.  
    |Noem hun aanknooppunten k1, k2, en k3 .  Volgens stelling 2 is er dan een punt k0 van de eerste brug zodat k1k0 en k2k0 en k3k0 alleen k0 gemeenschappelijk hebben.

Maar die tweede brug moet volgens deze stelling óók zo'n punt hebben! En dat kan niet. Als je het in de Jordankromme k1k2k0 kiest (zoals in de figuur hiernaast, dan kun je nooit k3 bereiken, en hetzelfde geldt voor k0'  in één van de andere gebieden.. 
 

  Beide gevallen leveren tegenstrijdigheden op, dus binnenbruggen kunnen elkaar niet overlappen. Op dezelfde manier geldt dat voor buitenbruggen.
■      
       

Toch nog een nieuwe term:

We noemen een binnenbrug  verplaatsbaar als de graaf ook heel makkelijk zó getekend kan worden (isomorf aan de vorige) dat deze brug een buitenbrug is geworden.
 
Stelling 4:  Een binnenbrug die elke buitenbrug vermijdt is verplaatsbaar.
       
Als een binnenbrug alle buitenbruggen vermijdt, dan liggen de aanknooppunten ervan allemaal in één facet van G aan de buitenkant van de cykel.
In dat facet kun je de binnenbrug tekenen. Hier zie je het in werking:
       

       
Het is natuurlijk logisch dat, als een graaf planair is, dat dan elke subgraaf ervan óók planair is.  En op dezelfde manier lijkt het me logisch dat, als een graaf een niet-planaire subgraaf bevat, dat de hele graaf dan ook niet planair is. We kennen al twee niet-planaire grafen, namelijk  K5 en K3,3.  Dat betekent het volgende:
       

G bevat K5 of K3,3   ⇒   G is niet planair
       
Niet heel spectaculair allemaal, maar nou komt het:  De Pool Kasimierz Kuratowski bewees dat je de implicatiepijl hierboven ook mag omdraaien!!!  Dát is wel spectaculair!  Kuratowski liet eigenlijk zien de enige twee niet-planaire grafen die we kennen in essentie K5 en K3,3 zijn!  Alle anderen zijn daarop terug te herleiden.

Hij leverde het bewijs in 1930.  Dat betekent dat we, voor wiskundige begrippen, hier bezig zijn met heel recente theorie!

Voor het bewijs zijn eerst nog wat hulpstellinkjes  (lemma's) nodig.
       
  L5. Scheur een niet-planaire graaf G in tweeën met als "scheurlijn" de verbinding k1k2  (neem die k1k2 in beide delen mee). Dan is minstens één van beide delen weer niet-planair. 
Hier zie je een plaatje met wat ik bedoel:  
       
   

       
    Stel dat G1 en G2 beiden wel planair zouden zijn.  Kies dan in de planaire tekening van G1 het facet waar zijde k1k2 aan grenst, en teken in dat facet de hele graaf G2.  Dan heb je weer een representatie van graaf G gekregen, maar nu planair. Dat kan niet, want G was immers niet-planair.
  ■    
       
  L6. Stel dat G een niet-planaire graaf is, die geen K5 of K3,3 bevat en zo weinig mogelijk verbindingslijnen heeft.
Dan is G een 3-verbonden graaf.

Stel dat G niet 3-verbonden is. Dan zijn er dus 2 knooppunten k1 en k2 die een  puntsnede vormen.  Maak dan de grafen  G1 en G2 zoals hierboven door k1k2 weg te laten. Volgens het vorige lemma (L5) is dus één van beiden niet-planair.  Stel G1......
Omdat het aantal verbindingslijnen van G1 kleiner is dan dat van G  moet G1 dus wél  K5 of K3,3 bevatten  (G was immers degene met de minste verbindingslijnen). Maar dan bevat G óók K5 of K3,3, immers  G bevat G1.

Dat kan niet, dus is G wel 3-verbonden  (dan kan hij tenminste door één lijn weg te laten niet uit elkaar vallen).
  ■    
       
En dan eindelijk de stelling van Kuratowski....

Even als geheugensteuntje; we moesten het volgende nog bewijzen:
       

  G is niet planair    ⇒  G bevat K5 of K3,3

       
Stel weer dat we een niet-planaire graaf G hebben die niet K5 of K3,3, bevat.  Kies voor G weer de kleinst mogelijk graaf waarvoor dat zo is. 
Dan is volgens L6 hierboven G dus een 3-verbonden graaf.
Kies een verbindingslijn k1k2 van G,  en noem de graaf waar die verbindingslijn uit wordt weggelaten H  (dus H = G - k1k2)
Omdat G  3-verbonden is, is H dan 2-verbonden.
Maar dan is er een cykel van H te vinden waar k1k2 een deel van is (dat is helemaal aan het eind van deze les over verbondenheid al bewezen).
Kies de cykel C van H die zoveel mogelijk verbindingslijnen in zijn binnengebied heeft.

Maar dan moeten alle buitenbruggen van C allemaal 2-bruggen zijn die k1k2 overlappen!!  Kijk maar:
       

       
Je ziet dat, zodra er een 3-brug (of hoger) of een niet-overlappende 2-brug bestaat,  er ook een grotere cykel mogelijk is, en dat in in strijd met het feit dat C de grootst mogelijk cykel was.
       
Dat betekent dat de buitenbruggen er allemaal uitzien zoals hiernaast.

En zelfs dat is niet waar!   Als er een derde knooppunt z in zo'n brug zit, dan valt G uit elkaar als je de knooppunten x en y weglaat. Immers dan is er geen mogelijkheid meer om k1, k2, x en y aan elkaar te krijgen.  Maar G was 3-verbonden, dat zagen we al, dus die kan nooit uit elkaar vallen door 2 knooppunten weg te laten.
Kortom:  de buitenbruggen zijn allemaal enkele verbindingslijnen zoals hiernaast.  

       
Nou weten we verder dat niet alle binnenbruggen van G verplaatst kunnen worden. Als dat wel kon, nou dan zou ik ze allemaal verplaatsen naar het buitengebied, en dan lijn k1k2 middendoor C trekken, en dan heb ik een planaire graaf G gekregen!  Dus er is minstens één binnenbrug die verspringend is met een buitenbrug (zodat íe niet verplaatst kan worden).

Dan moet er ook minstens één binnenbrug B zijn die zowel verspringend is met een buitenbrug als met k1k2.
Als immers alle binnenbruggen OF niet met een buitenbrug verspringend zijn (dan kunnen we ze naar buiten verplaatsen en k1k2 verbinden) OF niet met k1k2  (dan hoeven we ze niet te verplaatsen want dan kunnen we k1k2 toch al verbinden)  dan is er een binnenverbinding  k1k2 te maken en dan was G planair.
Hier zie je de vier mogelijkheden nog een heer getekend:
       

       
In het eerste en derde geval kun je k1k2 gewoon tekenen en is G planair. In het tweede geval kun je de rode brug verplaatsen en is G weer planair.  Alleen het laatste geval zorgt ervoor dat G niet-planair is.

Stel dat de blauwe buitenbrug waar die rode B verspringend mee is (degene die dus de route k1k2 bederft) aanknopingspunten  x en y heeft.
Dan zijn er voor de aanknopingspunten van B  twee mogelijkheden, elk weer gesplitst in 2 varianten.
       
  1. Minstens één aanknooppunt van B is niet gelijk aan k1, k2, x of y
Dan zijn ze meteen allemaal verschillend, want anders krijg je dat verspringend-zijn niet voor elkaar.

Kies één van die punten (b1) in het stukje k1x.  Omdat de situatie symmetrisch is mag dat (anders geef je de knooppunten gewoon een andere naam).

Dan heb je de volgende twee mogelijkheden.
       
   

       
    Ga het zelf maar na; dit zijn de enige varianten waarvoor de rode knooppunten zowel met de blauwe punten als met de zwarte punten verspringen (rechts moeten er daarom wel 3 aanknooppunten op de cykel liggen)
In de rechterfiguur heb ik stiekem stelling 2 hierboven gebruikt:  er is zo'n derde knooppunt te vinden.

Maar kijk eens wat hier aan de hand is:
       
   

       
    Beide varianten bevatten een K3,3!
       
  2. De aanknooppunten van B zitten bij  k1, k2, x en y
Omdat B met beiden verspringt, moeten dus alle vier deze punten wel aanknooppunten zijn (Ga maar na dat bij 2 of 3 aanknooppunten altijd minstens één van de "verspringendheden" niet klopt).
Nou zijn er voor de routes  xy  en  k1k2 van die brug twee mogelijkheden:  ze hebben één knooppunt gemeenschappelijk OF ze hebben meer dan één knooppunt gemeenschappelijk  (nul kan niet, want ze horen wel bij dezelfde brug).
Dat geeft de volgende twee tekeningen:
       
   

       
Kortom:  bij alle mogelijkheden komen we (als we eisen dat een graaf niet-planair is) een variant van K3, 3 of K5 tegen.
Je zou K3,3 en K5 kunnen zien als de "basisvormen van niet-planaire grafen"
■      
       

© h.hofstede (h.hofstede@hogeland.nl)