WisFaq!

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 waarbij twee knopen door meer dan één boog met elkaar verbonden zijn.

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 Tavernier
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