Graf teori

[atrogulma]

Hei

Hvordan defineres egentlig en Euler-vei og en Euler-krets ?Hvis det er en betingelse at alle kantene skal benyttes for at en graf skal ha en euler-vei er det en krav om hvor mange ganger skal de besøkes ? Hva med hjørner kan de besøkes mer en enn gang her også eller ? Takk på forhånd

[Karl_Erik]

Hei! En Eulervei i en graf er en vei der du går gjennom grafen og går på alle kanter, men kun går på en kant én gang. En Eulerkrets er en Eulervei som begynner og slutter i samme node.

Eulerveier og Eulerkretser er i prinsippet kun interessert i kantene i grafen i den forstand at en Eulervei skal bruke hver kant nøyaktig én gang, og at alle skal benyttes, men hvor mange ganger du besøker hjørnene er valgfritt.

[atrogulma]

hmm er det ikke Euler-sti og Euler -sykler da ?

[Karl_Erik]

I mitt hode skulle det være andre ord for samme sak, men det er veldig mulig jeg bruker terminologien feil.

[anlif]

I mitt hode skulle det være andre ord for samme sak, men det er veldig mulig jeg bruker terminologien feil.

har hørt begge brukt av foreleser i diskret matematikk (altså de betyr det samme)

[Gustav]

Eulersti og -vei er det samme ja. På samme måte er Eulerkrets og -sykel det samme.

[atrogulma]

Nå jeg er klar over definisjon på Euler-vei/sti der å ha med alle kantene men bare engang og at nodene kan være med flere ganger.

Hvis en Euler-sykel/krets er en enkelt sykel som inneholder alle kantene i grafen bare engang og som starter og slutter i samme node.

Men i en enkelt sykel kan vi ikke bruke nodene mer enn en gang(unntak start og sluttnoden) betyr det at i en Euler-sykel alle kantene skal være med og at nodene og kantene skal IKKE gjentas ?? jeg er litt forvirret av alle disse begrepene :S