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

Verbondenheid.
       
Een vorige les heb ik de "graad van verbondenheid" van een graaf besproken. Dat was n getal dat zo ongeveer aangaf hoe sterk de punten van een graaf met elkaar verbonden zijn.
Deze les gaan we de "mate van verbondenheid" van een graaf wat beter en uitgebreider bestuderen. Van de grafen hieronder zul je intutief wel zien dat van links naar rechts de mate van verbondenheid toeneemt. 
       

       
Maar hoe zit het met nummer 3 en nummer 4?  Die hebben evenveel verbindingslijnen, dus de graad van verbondenheid is gelijk.  Is er toch verschil in verbondenheid......?

We gaan er vooral naar kijken hoe snel een graaf uit elkaar valt (niet meer samenhangend is) als we lijnen of knopen weglaten.  Daarom eerst maar weer wat termen:
       
een lijnsnede  is een verzameling van verbindingslijnen van een graaf zodat de graaf niet meer samenhangend is als je die verzameling eruit weglaat.  Een k-lijnsnede is een lijnsnede die uit k verbindingslijnen van de graaf bestaat.
een puntsnede is een verzameling van knooppunten van een graaf zodat die graaf niet meer samenhangend is als je die verzameling eruit weglaat.  Een k-puntsnede is een puntsnede die uit k knooppunten van de graaf bestaat.

de puntverbondenheid  p  van een graaf  is de kleinste waarde van k waarvoor een  puntsnede bestaat.  Dat is dus het minst aantal knooppunten dat je weg kunt laten om de graaf uit elkaar te laten vallen. En het zal je niet verbazen dat de lijnverbondenheid l  het zelfde is, maar dan met weglaten van zo weinig mogelijk verbindingslijnen.
       
Zo heeft graaf 1 hierboven punt- en lijnverbondenheid beiden 0 (hij is niet eens samenhangend).
En nu valt ook een verschil tussen de grafen 3 en 4 op:   3 heeft lijnverbondenheid   l = 1  (je kunt die ene "loshangende" verbindingslijn weglaten), en 4 heeft lijnverbondenheid l = 2.
       
Stelling: 

   p    l  ≤  δ

       
(δ is de laagste graad van alle knooppunten, weet je nog?)
ofwel:  "een graaf valt sneller uit elkaar als je knooppunten weglaat dan als je verbindingslijnen weglaat".
       
  l  ≤  δ  is nogal logisch, immers je kunt van het punt met laagste graad gewoon alle verbindingen weglaten, dan valt dat punt eraf,  en dus de graaf uit elkaar.
       
  p   l   is ook vrij logisch eigenlijk.
Stel dat er een manier is om met l lijnen weglaten de graaf uit elkaar te laten vallen.
Een lijn laten wegvallen kun je ook tot stand brengen door n van zijn eindpunten te laten wegvallen. Dus l lijnen weg laten vallen kan je net zo goed doen door evenveel eindpunten te laten wegvallen. Daarom zal p nooit groter dan l zijn.

     
       
Stelling:

verbindingslijn V  is een lijnsnede  ⇔  V komt in geen enkele cykel voor  

       
Het bewijs moet uiteraard beide kanten op geleverd worden (⇔):
Stel dat V de knooppunten K1 en K2 verbindt, in de cykel   K1-(V)-K2K3K4K5...K1  Als V dan weggelaten wordt, zijn K1 en K2 nog steeds verbonden, namelijk via de andere kant rond de cykel  (K2K3...K1).
Stel dat V de knooppunten K1 en K2 verbindt en in geen enkele cykel voorkomt. Dan zijn K1 en K2 niet meer verbonden als V weggelaten wordt. Immers als dat wl zo was, via route K1KiKj...K2 , dan was er oorspronkelijk een cykel  K2-(V)-K1KiKj...K2
     
       
Blokken.
       
Een graaf waarvan geen enkel knooppunt direct een puntsnede is, heet een blok.  't Is precies wat je je erbij voorstelt:  een blok is best solide; die valt dus echt niet zomaar bij het minste of geringste uit elkaar!!
Dat betekent bijvoorbeeld dat elk blok (met minstens 3 knooppunten)  puntverbondenheid minstens 2 heeft.

Een blok van een grotere graaf is een zo groot mogelijke deelgraaf met die blok-eigenschap.
Een graaf kun je op die manier opgebouwd denken uit blokken  (vaak trouwens maar eentje).

Routes in een graaf noemen we disjunct als ze geen enkel knooppunt gemeenschappelijk hebben.

Stelling.

       

een graaf  heeft puntverbondenheid minstens 2 

elk paar knooppunten is minstens door twee disjuncte routes met elkaar verbonden.

       
De pijl  ⇐  is wel vrij logisch, denk ik  (als er aan elk punt 2 routes zitten, dan valt de graaf niet uit elkaar als je dat punt weglaat)
Maar hoe is met die pijl 
???
Dat gaan we bewijzen met volledige inductie. We bekijken daarvoor de afstand d(k1, k2) tussen twee knooppunten. Dat is het aantal verbindingslijnen in de kortste route k1k2 (precies wat je je erbij voorstelt).

Als twee punten afstand 1 hebben en de graaf is 2-verbonden, dan is  k1k2 dus geen directe lijnsnede, dus moeten er minstens 2 verbindingen tussen k1 en k2 zijn.

Stel nu dat de stelling klopt voor alle punten op afstand minder dan d van elkaar  (inductie-aanname)
Kies dan twee punten k1 en k2 met afstand d tot elkaar.  (zie de figuur hieronder). Bekijk nu de route  k1k2.  Stel dat  k3 het n na laatste knoppunt (vlak vr k2 dus) op deze route is. Omdat de afstand van k1 tot k3 dan  gelijk is aan  k - 1 is zijn er twee  disjuncte routes  k1k3  (inductie-aanname)Die zijn hieronder blauw getekend
       

       
Dan is de route  k1k4k2  rechts groen,  disjunct van de oorspronkelijke k1k3k2  bovenlangs. Dus weer zijn er twee disjuncte routes van k1 naar k2.

     
 
Gevolgjes van deze stelling:  (voor grafen met puntverbondenheid minstens 2) 
   

voor zo'n graaf  liggen elke twee knooppunten op een cykel. Er zijn immers twee disjuncte routes, dus neem de ene route "heen" en de andere "terug" en voil:  je hebt een cykel.

voor zo'n graaf liggen elke twee verbindingslijnen in een cykel.
Kies maar twee willekeurige verbindingslijnen. Maak nu een nieuwe graaf door op die verbindingslijnen twee nieuwe knooppunten kx en ky te kiezen.  Die nieuwe graaf is dan weer 2-verbonden  ('t is weer een blok), dus er is een cykel van kx naar ky en dat kan alleen via de verbindingen V1 en V2.
       
Later zullen we nog een uitbreiding op deze gevolgjes zien; de stelling van Menger.

We hebben trouwens deze les erg veel (haast alle) aandacht aan 2-verbonden grafen. Dat is niet omdat dat nou een speciale hobby van mij is, maar omdat we de eigenschappen van zulke grafen later nog weer nodig zullen hebben.
       
OPGAVEN
       
1. a. Een graaf is 2-lijn verbonden  ⇔   elk paar knooppunten is verbonden door tenminste twee lijn-disjuncte routes.
Toon dat aan.
       
  b. Stel dat K1 en K2 in een 2-verbonden graaf door een route R worden verbonden. Laat met een voorbeeld zien dat er dat niet altijd  een tweede route (disjunct van R) in de graaf hoeft te bestaan.
       
2. G heeft geen even cykels ⇔  elk blok van G is f K1, f K2 f een oneven cykel
Toon dat aan.
       
       

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