Добрый вечер, решаю контрольную по дискретной математики и наткнулся на такую штуку:

Коэффициент связности графа

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

wiki:Словарь_терминов_теории_графов

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

Пожалуйста, растолкуйте

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

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

http://dic.academic.ru/dic.nsf/enc_mathematics/1261/ГРАФА

хмммм т.е.

http://s017.radikal.ru/i420/1212/a3/453e4ee754c8.png

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

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

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

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

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

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

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

(12) т.е. если бы было что-то на подобии
http://s019.radikal.ru/i631/1212/49/46d82f5757d9.png
то это уже был бы 4х связный?

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

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

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

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

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

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

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

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

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

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

По ссылке из (5).

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

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

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

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

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

К твоему подходит, если забить на направления.

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

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