Даден е неориентиран граф G=(V,E)

[plamen245]

Здравейте,

От скоро започнах да изучавам дискретна математика - теория на графите. Учителят ни даде за решаване следната задача, за която си нямам и идея как се решава:

Даден е неориентиран граф G=(V,E). Да се определи броят на компонентите на свързаност на G.

Ще Ви бъда много много благодарен, ако можете да я решите и да ми я обясните, как точно се решава.
Благодаря Ви предварително за отговора!

[allier]

С компютър се решава ...

[plamen245]

Как така с компютър?

[allier]

Първо, за да намериш компонентите на граф, трябва да ти е предварително зададен този граф, нали? Т.е. трябва да знаеш къде са ребрата или с други думи матрицата на свързаност. Алгоритъм за намиране на компонентите на свързаност има, но по принцип тези дейности се извършват с компютърна програма. Ако е малък графът или е специфичен, може да се реши и на ръка.

Ето ти един примерен алгоритъм:

Започваш от определен връх и го маркираш с числото 1. Всички върхове, които са свързани с този връх, също маркираш с 1. Всички върхове, които са свързани с тези върхове, пак маркираш с 1. И т.н. - докато спреш да получаваш нови върхове. След това ако в графа няма повече върхове, то той самият е свързан и има 1 единствена компонента (маркирана с 1). Ако има още върхове, маркираш някой от тях с 2, и правиш същата процедура. В крайна сметка, колкото числа са ти нужни за маркиране, толкова компоненти има графа.