Beste mensen, De volgende vraagstukken heb geprobeerd te beantwoorden. Kunt u mij vertellen of ik in de juiste richting naar de antwoorden heb gezocht? Alvast bedankt. Rosita vraag1 : bestaat een 26 reguliere niet bipartiete graaf die niet-Eulers is? mijn oplossing : de graad is even en de stelling van Euler zegt dat een graaf dan en slechts dan een Euler graaf is als alle punten een even graad hebben dus de graaf is wel Eulers vraag 2: Bestaat een 26 reguliere niet-bipartiete graaf die 2 kleurbaar is? mijn oplossing: bestaat niet omdat alleen een bipartiete graaf 2 kleurbaar is. vraag 3: bestaat een oneven gradige bipartiete volledige graaf? mijn oplossing: graad van de graaf is oneven hij is dus 'oneven' regulier. Algemene vorm van een bipartiete graaf is Kn,m . Als hij regulier is dan is n = m.In dit geval is het niet zo.
Rosita
Student hbo - vrijdag 12 september 2008
Antwoord
Je oplossingen lijken me behoorlijk goed:
1. Ik dacht eerst dat dit juist was, maar: de stelling zegt dat een samenhangende graaf Eulers is dan en slechts dan als alle punten even graad hebben. Over samenhangend is hier niets gezegd. Het is dan niet zo moeilijk een tegenvoorbeeld te creëren: neem K27 en zet er nog eens K27 naast. Die graaf met 54 toppen is 26-regulier, niet-bipartiet en niet-Eulers want in een niet-samenhangende graaf kan je natuurlijk geen Eulercircuit maken. 2. Klopt helemaal. 3. Wat bedoel je met 'In dit geval is het niet zo'? Zelfs als n=m (wat volgens mij niet uit de opgave volgt(*)) kan je nog altijd Kn,n bekijken: die is n-regulier, en bipartiet volledig. K1,1 of K3,3 zijn dus voorbeelden.
(*) hangt af van wat je bedoelt met 'oneven gradig': betekent dit dat elke top een oneven graad heeft, of betekent het dat elke top dezelfde graad heeft en dat die graad oneven is (dus n-regulier met n oneven)? In die tweede interpretatie volgt dan inderdaad dat n=m.
Ook de formulering 'bipartiete volledige graaf' is nogal ongelukkig: waarschijnlijk bedoelt men inderdaad een Kn,m maar strikt genomen vraag je zo naar een volledige graaf Kn die ook nog eens bipartiet is. Hoedanook blijft K2=K1,1 een correct voorbeeld.
