Количество ребер в графе

@AlexKolc · Регистрация: 14.09.2013

Author24 — интернет-сервис помощи студентам

Какое максимальное количество ребер может быть в простом слабо связном ориентированном графе на 10 вершинах, не являющемся сильно связным?

@kabenyuk · 10.04.2015, 17:34

Похоже 45 - максимально возможное число ребер простого графа. Строим такой граф так. Выбираем некоторую вершину, скажем А. На остальных 9-ти вершинах проводим все возможные ребра. Вершину же А соединяем ребрами со всеми 9-тью вершинами и направляем их к вершине А.
Такой граф слабо связен, но не является сильно связным, так как из А ни в одну другую вершину нет пути.

@AlexKolc · 11.04.2015, 10:37 **[ТС]**

kabenyuk, нет не 45, там 10*9-10 =81

@kabenyuk · 14.04.2015, 19:27

Сообщение от AlexKolc

10*9-10 =81

А может 10*9-9=81.

@AlexKolc · 15.04.2015, 16:01 **[ТС]**

kabenyuk, да, точно, спасибо

@AlexKolc 191 / 161 / 116 Регистрация: 14.09.2013 Сообщений: 302
		1
	Количество ребер в графе 09.04.2015, 19:36. Показов 15185. Ответов 4 Метки нет (Все метки) Какое максимальное количество ребер может быть в простом слабо связном ориентированном графе на 10 вершинах, не являющемся сильно связным? 0

@kabenyuk $Эксперт по математике/физике$ 4166 / 3038 / 914 Регистрация: 19.11.2012 Сообщений: 6,182
	10.04.2015, 17:34	2
	Похоже 45 - максимально возможное число ребер простого графа. Строим такой граф так. Выбираем некоторую вершину, скажем А. На остальных 9-ти вершинах проводим все возможные ребра. Вершину же А соединяем ребрами со всеми 9-тью вершинами и направляем их к вершине А. Такой граф слабо связен, но не является сильно связным, так как из А ни в одну другую вершину нет пути. 0

@AlexKolc 191 / 161 / 116 Регистрация: 14.09.2013 Сообщений: 302
	11.04.2015, 10:37 [ТС]	3
	kabenyuk, нет не 45, там 10*9-10 =81 0

@kabenyuk $Эксперт по математике/физике$ 4166 / 3038 / 914 Регистрация: 19.11.2012 Сообщений: 6,182
	14.04.2015, 19:27	4
	Сообщение от AlexKolc 109-10 =81 А может 109-9=81. 1

@AlexKolc 191 / 161 / 116 Регистрация: 14.09.2013 Сообщений: 302
	15.04.2015, 16:01 [ТС]	5
	kabenyuk, да, точно, спасибо 0