WisFaq!

De digitale vraagbaak voor het wiskundeonderwijs

HOME

samengevat

\require{AMSmath}

Grafen

Is een volledige graaf regulier?

Waarde wiskundige,

Het probleem is op zich eenvoudig. Het gaat over de (on)duidelijkheid van definities.

Ik ben stagair wiskunde en in een stageles in het 4e jaar heb ik gezegd dat volledige grafen regulier zijn.
Ik heb zelf nooit grafentheorie gehad en heb dus geen oude cursus om op terug te vallen. Ik gebruik Nando 4, 14 Grafen.

De pertinente definities daarin zijn:

Een graaf waarin alle knopen dezelfde graad hebben, is een reguliere graaf.
Een graaf heet volledig als elke knoop in de graaf verbonden is met alle andere knopen in de graaf.
Een multigraaf is een graaf waarbĳ twee knopen door meer dan één boog met elkaar verbonden zĳn.

Toen ik mijn uitspraak deed bedacht ik dat ze niet klopt. Volgens bovenstaande definities kan een volledige graaf knopen hebben met een hogere graad dan andere knopen (door extra bogen te hebben) en dus niet regulier zijn.

Ik vind maar weinig definities online. De chatbots GPT-4 en Claude 2 komen echter met varianten af. Zo zegt Claude 2 bv. dat een reguliere graaf een graaf is waarbij elke knoop hetzelfde aantal buren heeft.

Hoe zit het echt in elkaar?

Met vriendelijke groeten,
Frank
Frank
24-3-2024

Antwoord

De terminologie van de grafen is, helaas, niet geheel gestandaardiseerd.
In het boek Hoofdstukken uit de Combinatoriek is een graaf wat jij een multigraaf noemt en heet wat jij een graaf noemt heet daar een enkelvoudige graaf.

Je moet dus vantevoren afspreken wat je met `graaf' bedoelt. Als je bedoelt dat tussen twee knopen ten hoogste één tak loopt en er ook geen lussen zijn. Dan is de volledige graaf $K_n$ regulier omdat elk punt dezelfde graad $n-1$ heeft.

Uit jouw drie definities leid ik af dat je uitspraak wel klopte had omdat je onderscheid maakt met de term `multigraaf'; dat klinkt alsof voor jou `graaf' niet hetzelfde betekent multigraaf en dus de definitie uit de vorige alinea gebruikt.

Voor later: kijk altijd eerst in het onderwijsmateriaal om te zien wat de definities zijn en formuleer je uitspraken zó dat ze daarmee in overeenkomst zijn.
kphart
24-3-2024

Re: Is een volledige graaf regulier?

Bedankt voor de snelle reactie.

Ik snap niet waarom de uitspraak toch juist zou zijn. Een graaf is inderdaad geen multigraaf, maar een multigraaf wel een graaf (neem ik aan), net zoals een veelhoed geen vierhoek is, maar een vierhoek geen veelhoek.

Het begrip enkelvoudige graaf is in het leerboek niet gedefinieerd. Op basis van de vorige definities zou ik zeggen dat dat best gedefinieerd wordt als een graaf die geen multigraaf is. Dan zijn alle grafen ofwel multigraaf, ofwel enkelvoudige graaf.
Frank
25-3-2024

Antwoord

Daar heb je het al: ik ben opgegroeid met grafen die enkelvoudigheid in de definitie hebben staan. "Elke graaf is enkelvoudig en zonder lussen tenzij uitdrukkelijk anders vermeld."

Je had dus voor je drie pertinente definities nog de definitie van `graaf' moeten vermelden. Dan was alles ondubbelzinnig geweest.

Wat daar nog bij komt is dat veel grafentheoretici het over "de volledige graaf op $n$ punten" hebben, en dan de graaf bedoelen met $n$ punten en tussen elk tweetal punten precies één tak, die heet dan $K_n$ en is duidelijk regulier.

kphart
25-3-2024