Отиди на
Форум "Наука"

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


plamen245

Recommended Posts

  • Потребител

Здравейте,

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

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

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

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

Link to comment
Share on other sites

  • Потребител

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

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

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

Link to comment
Share on other sites

  • Потребител

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

Link to comment
Share on other sites

Напиши мнение

Може да публикувате сега и да се регистрирате по-късно. Ако вече имате акаунт, влезте от ТУК , за да публикувате.

Guest
Напиши ново мнение...

×   Pasted as rich text.   Paste as plain text instead

  Only 75 emoji are allowed.

×   Your link has been automatically embedded.   Display as a link instead

×   Your previous content has been restored.   Clear editor

×   You cannot paste images directly. Upload or insert images from URL.

Зареждане...

За нас

Вече 17 години "Форум Наука" е онлайн и поддържа научни, исторически и любопитни дискусии с учени, експерти, любители, учители и ученици.

За своята близо двайсет годишна история "Форум Наука" се утвърди като мост между тези, които знаят и тези, които искат да знаят. Всеки ден тук влизат хиляди, които търсят своя отговор.  Форумът е богат да информация и безкрайни дискусии по различни въпроси.

Подкрепи съществуването на форумa - направи дарение:

Дари

 

 

За контакти:

×
×
  • Create New...