2 задачи по графам и доказательство.

@TI_ProJecT · Регистрация: 13.03.2011

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

Помогите в решении данных задач, нужен не только ответ, но и расписать почему.

1)Всегда ли дополнение простого несвязного графа будет связным графом?
Мое решение:

Данное утверждение будет выполняться всегда: дополнение несвязного графа будет связным графом.
Данный вывод следует из того, что при построении дополнения для исходного графа мы достраиваем его до полного графа, а так как у нас был несвязный граф, то следовательно, имеется хотя бы одна вершина в графе, которая не связана ни с одной другой вершиной этого графа, и при построении дополнения для этого графа мы получим связный граф, так как именно эта вершина будет соединена со всеми другими вершинами данного графа, а следовательно, мы получим связный граф.

Замечание:

Вы пишите "а так как у нас был
несвязный граф, то следовательно,
имеется хотя бы одна вершина в графе,
которая не связана ни с одной другой
вершиной этого графа" - но ведь это не
верно в общем случае. Каждая их
компонент связности несвязного графа
может иметь много вершин

2)Какое наибольшее число точек сочленения может быть в связном графе с n вершинами?
Мое решение:

Точкой сочленения называется вершина графа, при удалении которой число связных компонент графа возрастает.
Учитывая то, что концевые вершины графа не являются точками сочленения, проанализируем различные виды графов:
Цепь - Pn - максимальное число точек сочленения будет равняться n – 2.
Цикл - Cn. Наибольшее число точек сочленения в этом графе будет составлять n – 2.
Звезда – Sn. В этом графе всего 1 точка сочленения – центральная.
Колесо – Wn. В данном графе максимальное число точек сочленения в этом графе будет равняться n – 1.
Проанализировав полный граф – Kn, приходим к выводу, что максимальное число точек сочленения в нём будет равняться n – 1.
Из вышеперечисленных выводов можно сделать вывод, что наибольшее число точек сочленения в связном графе с n вершинами будет равняться n-1.

Замечание:

Цикл - Cn. Наибольшее число точек
сочленения в этом графе будет
составлять n – 2.
Колесо – Wn. В данном графе максимальное
число точек сочленения в этом графе
будет равняться n – 1.
Проанализировав полный граф – Kn,
приходим к выводу, что максимальное
число точек сочленения в нём будет
равняться n – 1.

Это все неверно

Байт · 22.12.2011, 12:55

1) Компонент связности у несвязного графа как минимум 2: А1 и А2. В дополнительном графе любая вершина х из А1 соединена со всеми вершинами из других компонент связности. Если в А1 больше нет вершин, то все доказано. Если есть y != x принадлежащая A1, то возьмем вершину z из А2. Она инцендентна и y и х, т.е есть путь x - z - y.
По сути мы доказали более сильное утверждение, что дополнительный граф имеет максимальную длину пути = 2

Добавлено через 4 минуты
2) Замечание совершенно справедливо. У цикла, колеса, полного графа точек сочленения вообще нет.
А у цепи действительно n-2 точки сочленения. Это и есть максимальное число

Добавлено через 8 минут

Хотел узнать то что вы написали в теме, можно добавить к моему ответу? И получится полный ответ, так? Или что то еще необходимо добавить?

По первой задаче можете спокойно выкинуть все свое доказательство и заменить его приведенным.
По второй из своего выкидываете все кроме ЦЕПИ. Ну и нужно еще доказать, что больше n-2 точек сочленения быть не может. Вот как бы это доказать построже - чего-то в голову не приходит.

Новые блоги и статьи Все статьи Все блоги /
Запрет удаления строк ТЧ документа при определенном условии Maks 19.04.2026 Алгоритм из решения ниже реализован на примере нетипового документа "Аккумуляторы", разработанного в конфигурации КА2. У данного документа есть ТЧ, в которой в зависимости от прав доступа. . .	Модель заражения группы наркоманов alhaos 17.04.2026 Условия задачи сформулированы тут Суть: - Группа наркоманов из 10 человек. - Только один инфицирован ВИЧ. - Колются одной иглой. - Колются раз в день. - Колются последовательно через. . .	Мысли в слух. Про "навсегда". kumehtar 16.04.2026 Подумалось тут, что наверное очень глупо использовать во всяких своих установках понятие "навсегда". Это очень сильное понятие, и я только начинаю понимать край его смысла, не смотря на то что давно. . .	My Business CRM MaGz GoLd 16.04.2026 Всем привет, недавно возникла потребность создать CRM, для личных нужд. Собственно программа предоставляет из себя базу данных клиентов, в которой можно фиксировать звонки, стадии сделки, а также. . .
Знаешь почему 90% людей редко бывают счастливыми? kumehtar 14.04.2026 Потому что они ждут. Ждут выходных, ждут отпуска, ждут удачного момента. . . а удачный момент так и не приходит.	Фиксация колонок в отчете СКД Maks 14.04.2026 Фиксация колонок в СКД отчета типа Таблица. Задача: зафиксировать три левых колонки в отчете. Процедура ПриКомпоновкеРезультата(ДокументРезультат, ДанныеРасшифровки, СтандартнаяОбработка) / / . . .	Настройки VS Code Loafer 13.04.2026 { "cmake. configureOnOpen": false, "diffEditor. ignoreTrimWhitespace": true, "editor. guides. bracketPairs": "active", "extensions. ignoreRecommendations": true, . . .	Оптимизация кода на разграничение прав доступа к элементам формы Maks 13.04.2026 Алгоритм из решения ниже реализован на нетиповом документе, разработанного в конфигурации КА2. Задачи, как таковой, поставлено не было, проделанное ниже исключительно моя инициатива. Было так:. . .