Irányítatlan gráfok

Hány 4 csomópontból álló, különböző irányítatlan gráf létezik?

Két gráfot különbözőnek tekintünk, ha a szomszédsági mátrixuk különböző.

• 24

• 4

Egy irányítatlan gráfnak 5 csomópontja és 9 éle van.

A következő számsorozatok közül melyik lehet a gráf csomópontjainak fokszáma?

• 4, 2, 6, 4, 2

• 2, 2, 1, 2, 2

• 1, 1, 1, 1, 1

• 4, 3, 3, 4, 4

Tekintsünk egy 60 csomópontból álló irányítatlan gráfot (csomópontjai 1-től 60-ig vannak számozva) melynek élei: [1,60], [60,20], [2,30] és [4,30].

Határozd meg hány összefüggő komponense van a gráfnak.

• 3

• 56

• 54

• 0

Tekintsünk egy 7 csomópontból álló irányítatlan gráfot (csomópontjai 1-től 7-ig vannak 26. számozva) melynek élei: [1,2], [1,3], [2,3], [2,4], [2,5], [2,6], [4,6], [5,7], [6,7].

Legkevesebb hány élet kell hozzáadni a gráfhoz, ahhoz hogy a gráf Euler-féle gráf legyen?

• 1

• 2

• 3

• 4

Egy irányítatlan gráf csomópontjainak halmaza: {1,2,3,4,5,6} és az élek halmaza:

{[1,2], [2,3], [3,4], [3,5], [4,5], [1,3], [2,6], [2,4], [4,6]}.

Legkevesebb hány élét törölhetjük a gráfnak, és melyek ezek az élek úgy, hogy a kapott parciális gráf

ne legyen összefüggő?

• 1

• 2

• 3

• 4