Связные графы

[analitik777]

Разбираюсь со статьёй на английском, в которой рассказывается про эластичную маршрутизацию.
Вот здесь можно её скачать : http://rghost.ru/48424226 (это обычный файлообменник, никому плюсы или минусы не идут если файл скачивается).
Что конкретно понимается под связным графом? Если перевёл правильно, то k-связный граф это граф, из которого нельзя сделать разьединённый граф, удаляя меньше k узлов... . Смотрел литературу (разумеется на русском) о связных графах, но пишут одну ерунду, в основном только про 1-связный граф, а нужно 2-, 3-связные.
Если кто знает литературу, покажите пожалуйста. Можем статью пообсуждать, кому интересно, вещь прикладная ))

[Deggial]

Тема перемещена из форума «Дискуссионные темы (М)» в форум «Помогите решить / разобраться (М)»
Перенёс в соответствующий раздел.
analitik777, убедительная просьба создавать темы в соответствующих разделах.

[nikvic]

analitik777 в сообщении #758386 писал(а):

Смотрел литературу (разумеется на русском) о связных графах, ... а нужно ... 3-связные.

Нет ли этого среди NP-полных?

[nikvic]

Сам и возражу - для тройки перебор невелик. А общая задача определения степени связности, похоже, NP-полна.

[VAL]

analitik777 в сообщении #758386 писал(а):

Что конкретно понимается под связным графом? Если перевёл правильно, то k-связный граф это граф, из которого нельзя сделать разьединённый граф

А этот термин Вы где-то почерпнули? Или это Ваше творчество? Обычно говорят об утрате связности.

Цитата:

удаляя меньше k узлов...

Это так называемая вершинная связность. Рассматривают еще и реберную.

Цитата:

. Смотрел литературу (разумеется на русском) о связных графах, но пишут одну ерунду, в основном только про 1-связный граф, а нужно 2-, 3-связные.

Вы уверены, что 1-связные графы - это ерунда?!
Тем более, что вряд ли авторы пишут именно об односвязных графах. Скорее всего, просто вводят понятие "связность", не углубляясь в детали.

Цитата:

Если кто знает литературу, покажите пожалуйста. Можем статью пообсуждать, кому интересно, вещь прикладная ))

Например, в книжке Емеличев и др. "Лекции по теории графов". Там есть отдельная глава про связность. И уж критерии 2-связности точно рассматриваются. У Зыкова (у него несколько книжек) тоже достаточно содержательно рассмотрены вопросы связности.

[analitik777]

VAL в сообщении #758657 писал(а):

analitik777 в сообщении #758386 писал(а):

А этот термин Вы где-то почерпнули?

Это я когда статью переводил, получилось перевести понятие с английского как-то так

-- Пт авг 30, 2013 03:56:02 --

ну одно-связные графы это конечно же не ерунда. я как раз о том и говорю, что пишут именно про 2- и 3- связные . Ой, спасибо за книжки, при много благодарен ))

[analitik777]

Deggial в сообщении #758454 писал(а):

Тема перемещена из форума «Дискуссионные темы (М)» в форум «Помогите решить / разобраться (М)»
Перенёс в соответствующий раздел.
analitik777, убедительная просьба создавать темы в соответствующих разделах.

Простите, у меня почему-то нету кнопочки "новая тема" в разделе "помогите разобраться". может быть я её не там ищу?

[Deggial]

analitik777 в сообщении #758853 писал(а):

Простите, у меня почему-то нету кнопочки "новая тема" в разделе "помогите разобраться". может быть я её не там ищу?

Она есть Она между списком архивных разделов и списков тем слева.