grafen verbondenheid

© 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 intuïtief 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 K₁ en K₂ verbindt, in de cykel K₁-(V)-K₂K₃K₄K₅...K₁ Als V dan weggelaten wordt, zijn K₁ en K₂ nog steeds verbonden, namelijk via de andere kant rond de cykel (K₂K₃...K₁).

⇒

Stel dat V de knooppunten K₁ en K₂ verbindt en in geen enkele cykel voorkomt. Dan zijn K₁ en K₂ niet meer verbonden als V weggelaten wordt. Immers als dat wél zo was, via route K₁K_iK_j...K₂ , dan was er oorspronkelijk een cykel K₂-(V)-K₁K_iK_j...K₂

■

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(k₁, k₂) tussen twee knooppunten. Dat is het aantal verbindingslijnen in de kortste route k₁k₂ (precies wat je je erbij voorstelt).

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

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

Dan is de route k₁k₄k₂ rechts groen, disjunct van de oorspronkelijke k₁k₃k₂ bovenlangs. Dus weer zijn er twee disjuncte routes van k₁ naar k₂.

■

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 k_x en k_y te kiezen. Die nieuwe graaf is dan weer 2-verbonden ('t is weer een blok), dus er is een cykel van k_x naar k_y en dat kan alleen via de verbindingen V₁ en V₂.

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 K₁ en K₂ 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 K₁, óf K₂ óf een oneven cykel Toon dat aan.