Diskret Matematik: måste en graf vara sammahängande för att ha en eulerväg?
Enligt min mattebok (Algebra och Diskret Matematik) samt vad jag har lyckats googla mig till så för att en graf ska kunna ha en Eulerväg så måste grafen vara sammanhängande.
Uppgiften jag satt med var att hitta hur många unika grafer med 4 noder(a,b,c,d) som innehåller en Eulerväg :
jag fick fram att svaret blev 3st
Graf 1: nod a och b med gradantal = 1, och nod cd med gradantal =2
Graf 2: nod a och b med gradantal =2, och nod c och d med gradantal =3
Graf 3: nod a med gradantal =3, nod b med gradantal = 1 plus nod c och d med gradantal 2
Men facit innehöll 2 grafer där vissa gradantal = 0
Upprepar frågan: Måste en graf vara sammanhängande för att innehålla en eulerväg?
Har mailat min lärare som är på semester så medans jag inväntar hans svar frågar jag här :)
Grafen får nog ha noder som saknar kanter. Man ska gå igenom alla kanter en gång var. Noder kan besökas flera gånger eller inte alls.
Laguna skrev:Grafen får nog ha noder som saknar kanter. Man ska gå igenom alla kanter en gång var. Noder kan besökas flera gånger eller inte alls.
Hmm okej, så då behöver grafen inte vara sammanhängande för att ha en Eulerväg?
Det stämmer, men alla kanter måste ligga i samma komponent.
