OFF: Помогите с дискретной математикой=)) #642517

#0 by men47

Добрый вечер, решаю контрольную по дискретной математики и наткнулся на такую штуку: Коэффициент связности графа Поисковая система не помогла, выдавала общие понятия, и лекции тоже не помогли, или я сильно уже туплю, хотя перерыл ничего не нашел. Помогите, пожалуйста, что это такое? и как это "едят"?=)

#1 by Волшебник

#2 by men47

из данной терминологии, я так и не понял, что это такое и чему коэффициент может ровняться=) Пожалуйста, растолкуйте

#3 by ERWINS

на сколько помню количество областей связности. т.е. областей не связанных друг с другом

#4 by Neg

Это компонента, наверное коэффициент и компонента одно и тоже.

#5 by miki

#6 by men47

хмммм т.е. мой граф получается не связный?... и коэффициент равен 1 или как он считается..

#7 by acsent

думаю это среднее расстояние между вершинами.

#8 by acsent

это 2х связный граф

#9 by men47

объясните, пожалуйста, как вы поняли, что это 2х связный граф, по какому принципу он так находится... пожалуйста=)

#10 by ERWINS

связность помойму определена для неориентированных графов

#11 by miki

а почему не слабосвязный?

#12 by acsent

Уьираем любое ребро - остается связным, значит 2х связный как минимум. Если убрать еще одно - то уже может стать несвязным - значит не 3х связный

#13 by men47

т.е. если бы было что-то на подобии то это уже был бы 4х связный?

#14 by acsent

тоже 2х. Не существует верщина, а любая вершина

#15 by men47

т.е. не должен разрушаться так называемый контур? поэтому там 2

#16 by acsent

это называется связность ))

#17 by men47

благодарю=) очень сильно выручил=) примерно понял=)

#18 by miki

почему убираешь ребро, а не вершину?

#19 by acsent

Что за граф без вершины?

#20 by miki

у ТС вершин в графе пять штук.

#21 by acsent

Кстати оказывается есть разные связности: реберная и вершинная

#22 by acsent

Вершины нет, а ребро идущее в нее есть? такого не может быть

#23 by miki

Числом вершинной связности графа G [обозначение ] наз. наименьшее число вершин, удаление к-рых (вместе с инцидентными им ребрами) приводит к несвязному графу или к графу, состоящему из одной изолированной вершины. Числом реберной связности [обозначение ] наз. наименьшее число ребер графа G, удаление к-рых приводит к несвязному графу. Граф G наз. k-связным, если и k-pеберно связным, если . По ссылке из .

#24 by miki

формулы-картинки не скопипастились, сорри.

#25 by men47

аааа... т.е. если к-связный, это надо решать через вершины, а не через ребер?=)... а там тогда как? если по простому=)

#26 by miki

одно-слабо-связный.

#27 by men47

а принцип нахождения? убрать любой граф? и что у нас тогда выйдет=)

#28 by miki

+ Граф называется односвязным (связным), если: У него одна компонента связности Существует путь из любой вершины в любую другую вершину Существует путь из заданной вершины в любую другую вершину Содержит связный подграф, включающий все вершины исходного графа Содержит в качестве подграфа дерево, включающее все вершины исходного графа (такое дерево называется остовным) При произвольном делении его вершин на 2 группы всегда существует хотя бы 1 ребро, соединяющее пару вершин из разных групп К твоему подходит, если забить на направления.

#29 by miki

Убери правую верхнюю вершину (с ребрами) - получишь граф с двумя компонентами.

#30 by men47

и тебе спасибо, добрый молодец=)) тоже выручил, теперь я знаю что существуют 2 разные связности=)))

OFF: Помогите с дискретной математикой=)) #642517

Похожие вопросы 1С

В этой группе 1С