SI-möte Grafteori

En stig som besöker varje hörn i grafen exakt en gång är en...

• Eulerväg

• Hamiltonstig

• Cyklisk grupp

• Konjugerad permutation

a → c → d → e → b → a

är en...

• Hamiltoncykel

• Hamiltonstig

• Eulercykel

• Eulerstig

Vilken/vilka av figurerna innehåller minst en Eulerkrets?

• Den vänstra

• Den högra

• Båda

• Ingen

Hur definieras en Eulerväg?

• En väg som går genom varje nod en gång

• En väg som går längs varje kant en gång

• En väg som går längs varje kant och börjar och slutar i samma nod

• En väg som är sandad

Låt G(V, E) vara en graf.
Vad beskriver:

 $\sum_{v\in V}^{ }\delta\left(v\right)=2\left|E\right|=2e$  

• Summan av alla hörn är hälften så stor som summan av alla kanter

• Summan av antalet kanter är dubbelt så stor som summan av alla hörns grader

• Summan av antalet kanter är hälften så stor som summan av alla hörns grader

I den kompletta grafen K_n har alla noder grad n-1

• Sant

• Falskt

Vilket påstående är felaktigt?

• En stig är en vandring där varje nod besöks högst en gång

• En cykel är en stig som börjar och slutar i samma nod

• En krets är en stig som börjar och slutar i samma nod

• Man kan få punktering på en cykel, men inte på en stig

Vilken graf är inte en planär graf?

• 
• 
• 
• 

Vad stämmer om grafen?

• Den är planär

• Den har en hamiltonstig

• Den är bipartit

• Den är enkel

Grafen har en...

• Eulerväg

• Eulerkrets

• Hamiltonstig

• Hamiltoncykel