Помощ !!! - задача - Теория на графите

[plamen245]

Здравейте,

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

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

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

Благодаря Ви предварително за отговора!

[Last roman]

едва ли ще намериш специалист по топология тук.

[Futurolog]

Нещо от тоя сорт няма ли да свърши работа:

Пишеш матрицата на инцидентност или както там се нарича. Това е квадратна таблица с рамер (брой на върховете)х(брой на върховете). Числата в нея показват колко ребра има между всяка една двойка върхове. Числата в N-тата итерация (N-тата степен) на матрицата показва колко пътя с дължина не повече от N има между всяка една двойка върхове. Нека N е броя на ребрата (броя на елементите във V). Понеже дължината на минимлния път между дадена двойка върхове е не повече от N, то повдигаш матрицта на степен N и нулите в първия ред например би трябвало да показват колко са компонентите на свързаност или поне така ми се струва.

Дано горните разсъждения помогнат, ако не... здраве да е, ще измислим друг начин!

[Futurolog]

Поправка, само с броене на нулите в първия ред няма да стане, но идеята е да се съобрази как от нулите на итерираната матрица да се преброят компонентите на свързаност на графа.

[alvassareiro]

Леле, ужас, какви са тея графи?