Теория графов. Вопросы. Задачи. Ответы.

Сообщение №6728 от CM 28 января 2003 г. 09:16
Тема: Теория графов. Вопросы. Задачи. Ответы.

алгоритм в графе
Сообщение от Real 27 января 2003 г. 15:52
Тема: алгоритм в графе

Народ, помогите найти алгоритм, который находит рёбра неориентированного графа, исключая которые граф разделяется на два подграфа.
Если конкретнее, то у нас есть две вершины (начало и конец) и нам нужно найти минимально количество рёбер, через которые идёт любой путь из вершины-начала в конец.
Спасибо!
-------------------------------------------------------------------------------

Re: алгоритм в графе spv 27 января 23:36
> Народ, помогите найти алгоритм, который находит рёбра неориентированного графа, исключая которые граф разделяется на два подграфа.
Вы хотите сказать-на две связные компоненты?
-------------------------------------------------------------------------------

Re: алгоритм в графе Denis 28 января 00:23
> Народ, помогите найти алгоритм, который находит рёбра неориентированного графа, исключая которые граф разделяется на два подграфа.
> Если конкретнее, то у нас есть две вершины (начало и конец) и нам нужно найти минимально количество рёбер, через которые идёт любой путь из вершины-начала в конец.
Я что-то не понял... Тебе кротчайший путь между указанными вершинами нужен?
-------------------------------------------------------------------------------


Отклики на это сообщение:

> Вы хотите сказать-на две связные компоненты?
Да, на две связанные компоненты. При чём так, что две изначально заданные вершины находятся в разных компонентах.
> Я что-то не понял... Тебе кротчайший путь между указанными вершинами нужен?
Нет, нужно минимальное сечение графа по рёбрам.


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

Чем могу.
Читал давно книжку польского математика в нашем переводе. Что-то вроде:
В. Липский, Комбинаторика для программистов. Мир, ~~1988
Там много разных алгоритмов и теорем про графы, минимальные деревья, компоненты, потоки, кратчайшие пути ...
Не уверен, что есть нужное. Возможны опечатки.


Т.к. по графам участники форума уже несколько раз открывали темы.
А также, учитывая, что иногда открывается тема с заголовком типа:
«Минимальное покрытие», из которого совершенно не ясно, что тема относится к графам, выделяется общая тема.
Пожалуйста, по тематике графов сообщения посылайте сюда.

Отклики на это сообщение (покзывать только заголовки - добавить ответ):

--------------------------------------------------------------------------------

6991: Минимальное покрытие m_cur 14 февраля 22:34
Верно ли утверждение, что в двудольном графе минимальное вершинное покрытие равно min {|U|,|V|}, где U,V кол-во вершин в каждой доле?

--------------------------------------------------------------------------------

6992: Re: Минимальное покрытие spv 14 февраля 23:18
> Верно ли утверждение, что в двудольном графе минимальное вершинное покрытие равно min {|U|,|V|}, где U,V кол-во вершин в каждой доле?
Нет. Легко придумать контрпример. Мощность наименьшего вершинного покрытия в двудольном графе равно мощности наибольшего паросочетания. Есть еще ряд формул, но явно через мощности долей этот параметр не выражается.



Сколько различных циклов в полном графе с эн вершинами (неориентированом)


> Сколько различных циклов в полном графе с эн вершинами (неориентированом)

циклов длины 2 ровно n*(n-1)/2
циклов длины 3 ровно n*(n-1)*(n-2)/3
и т.д.

Всего циклов
n*(n-1)/2 + n*(n-1)*(n-2)/3 + ... + n!/n


Здравствуйте,
Попалась такая интересная задача:
Привести пример графа, для которого не работает следующий алгоритм вершинного покрытия:
Находитя вершина с максимальной степенью, затем удаляется она и все ребра с ней инцедентные. Показать, что такой алгоритм не дает 2 аппроксимации.
Спасибо


> Здравствуйте,
> Попалась такая интересная задача:
> Привести пример графа, для которого не работает следующий алгоритм вершинного покрытия:
> Находитя вершина с максимальной степенью, затем удаляется она и все ребра с ней инцедентные. Показать, что такой алгоритм не дает 2 аппроксимации.
> Спасибо

Что значит "не дает 2 аппроксимации"? Не могли ли вы поподробнее?
А то, что такой граф существует, следует из того, что множество вершинных покрытий не образует матроид.


> > Здравствуйте,
> > Попалась такая интересная задача:
> > Привести пример графа, для которого не работает следующий алгоритм вершинного покрытия:
> > Находитя вершина с максимальной степенью, затем удаляется она и все ребра с ней инцедентные. Показать, что такой алгоритм не дает 2 аппроксимации.
> > Спасибо

> Что значит "не дает 2 аппроксимации"? Не могли ли вы поподробнее?
> А то, что такой граф существует, следует из того, что множество вершинных покрытий не образует матроид.

пусть OPT- это оптимальное решение, а OPT(ALG)-решение алгоритма. Тогда существует граф, для которого OPT(ALG)>= 2OPT+1. Вот такой граф и надо найти.



> Привести пример графа, для которого не работает следующий алгоритм вершинного покрытия:
> Находитя вершина с максимальной степенью, затем удаляется она и все ребра с ней инцедентные.

Расммотрим цикл из восьми вершин, скажем, 1-2-3-4-5-6-7-8-1
и добавим еще одну вершину 9 и соединим ее с вершинами 1,3,5,7.

Если применить указанный алгоритм к этому графу, то первой "вылетит" вершина 9. А потом еще какие-то четыре вершины, "покрывающие" цикл.
Минимальное же покрытие состоит из четырех вершин 1,3,5,7.

> Показать, что такой алгоритм не дает 2 аппроксимации.

Это хитрее - думать надо ;)



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


> ... критерий гамильтоновости графа - т.е. когда в графе есть гамильтонов обход (только без реберных графов, пожалуйста)

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

1. для графа со степенной последовательностью d_1,...,d_n, d_1>=d_2>=...>=d_n выполняется импликация (d_i<=i)==>(d_{n-i}>=n-i)
2. Для любых двух несмежных вершин x,y deg(x)+deg(y)>=n, где n>=3-число вершин графа.
3. граф G=H^2, где H-двусвязный граф с числом вершин >=3


Дан неориентированный граф G в виде матрицы,число k и ребро (x,y) в графе .Найти число путей длиной k между двумя любыми вершинами ,проходящих через ребро (x,y) ровно 1 раз.(Использовать метод Штрассена перемножения матриц и то что ,если граф в виде матрицы , то эта матрица в степени k даёт число путей длиной k между двумя любыми вершинами )


> ... критерий гамильтоновости графа - т.е. когда в графе есть гамильтонов обход (только без реберных графов, пожалуйста)

Если в любом подграфе на 4 вершинах хотя бы 4 ребра.


Кто знает,в каком состоянии гипотеза Улама :если даны два графа с одинаковым числом вершин (пусть х ) ,и для каждого построен набор из всех х его подграфов на х-1 вершине, то из совпадения двух наборов следует изоморфизм графов .


> Кто знает,в каком состоянии гипотеза Улама :если даны два графа с одинаковым числом вершин (пусть х ) ,и для каждого построен набор из всех х его подграфов на х-1 вершине, то из совпадения двух наборов следует изоморфизм графов .


Все в том же. Доказывается для отдельных классов графов, часто достаточно содержательных, но общего доказательства как не было, так и нет.

Зато недавно доказана сильная гипотеза Бержа. Так что не все так плохо в теории графов;)


Доброго дня всем!
У меня вопрос по теории графов. Столкнулся с конкретной задачи подчета максимального клика в производимом графе, заданного в свою очередь ввиде списка.
============
Например список имен врешин, представленный ниже:
yw
yu
yt
ys
yr
xw
xu
xt
xr
xs
wv
wp
vu
vt
vs
vr
ut
us
ur
up
ts
tr
tp
sr
sp
rp
qp
=======

Вопрос мой такого характера, если ли уже готовые решения на такого рода вопросы? Поиск по сети не дал определнного ответа. Не хочется изобретать велосипед.
В частности в книге, Steven S. Skiena "The Algorithm Design Manual" указывается на программы,похожие на решение по описанию но! .... ссылки мертвы.


Прошу помочь в этой новой для меня тематике. Заранее благодарен за отклики и советы, что самое важное и дорогое!
Алексей.
a_mor@mail.ru



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


Прошу прошения за некомпетентную постановку вопроса. Вы совершенно правы в следующем:
1. мной представлены только список ребер одного графа. Где вершины прописаны через символы: q, p, s….. (10). Общее количество равно 10.
2. задача поиска максимального клика в графе очень тесно стоит с решением NP-problem. В частности для представленного примера, поиск максимальной клики уже труден . Количество всевозможных подграфов из n вершин равно 2 в степени n. И практически только прямой проверкой их всех возможно найти максимальную клику.

В любом случае: спасибо за ответ.
Решения значит нет? Это последний мой вопрос?
Имея список такого вида, у нас нет решения найти максимальную клику?

С уважением, Ал.


> Прошу прошения за некомпетентную постановку вопроса. Вы совершенно правы в следующем:
> 1. мной представлены только список ребер одного графа. Где вершины прописаны через символы: q, p, s….. (10). Общее количество равно 10.
> 2. задача поиска максимального клика в графе очень тесно стоит с решением NP-problem. В частности для представленного примера, поиск максимальной клики уже труден . Количество всевозможных подграфов из n вершин равно 2 в степени n. И практически только прямой проверкой их всех возможно найти максимальную клику.

> В любом случае: спасибо за ответ.
> Решения значит нет? Это последний мой вопрос?
> Имея список такого вида, у нас нет решения найти максимальную клику?

> С уважением, Ал.

В случае задач на конечных множествах нельзя говорить, что решения нет. Оно всегда есть-перебор всех возможных вариантов. Другой вопрос насколько оно эффективно. В Вашем случае вариантов всего 2^10=1024. Перебрать столько подмножеств не представляет труда для любого компьютера начиная с программируемого калькулятора включительно.

Другое дело, если Вас интересует решения задачи о наибольшей клике в общем случае. Все опять же зависит от Ваших целей. ПОЛИНОМИАЛЬНОГО алгоритма нахождения наибольшей клики действительно не известно и есть основания полагать, что его не существует. С точки зрения теории это труднорешаемая (NP-трудная, если точнее) задача. В этом отношении все строго доказано. Впрочем, окончательно гарантировать отсутствие такого алгоритма пока недоказано P<>NP нельзя.

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


> Имея список такого вида, у нас нет решения найти максимальную клику?

Посмотрите сюда: http://www.busygin.dp.ua/npc.html
В частности, на QUALEX-MS и смежные ссылки.



Спасибо Вам spv!
Передо мной стоит задача именно, использую Ваши термины "...практических соображении, связанных с производством" такого рода. Список, приведенны мной есть не что иное, как перечисление выходов схемы. Выбор соответственно этих пар, обусловлен своими принципами.

Задача состоит в том, что по возможности (при наличии) определить максимальный клик по данному списку.

Например (на руках): cl=4 в подграфе, заданном парами : ut ts sx xu

ut
ts
( sx )
xt
cl=3 в подграфе, заданном парами : sr rp sp


sr
( rp )
pr

и так далее.


Провести сортировку.

Полностью согласен, что по мощности вычисления порядка 10 в 3 (1024) - не проблема. Но предел есть. Главное в этом случае думаю, порядок величины "cl". Чем эта величина больше в конкретном списке, тем грубо говоря больше ..... хотя бы время.
Мой вопрос был именно: есть ли такие готовые алгоритмы? Скрипты,кторые позволяют провести такую сортировку?
В моем вооружении Perl. Начал было реализовывать, но уткнулся в проблему бесконечного числа циклов. Конечно понимаю, это зависит напрямую от уровня. Но все же. Есть ли они?


С уважением , ал.





> > Имея список такого вида, у нас нет решения найти максимальную клику?

> Посмотрите сюда: http://www.busygin.dp.ua/npc.html
> В частности, на QUALEX-MS и смежные ссылки.

Благодарю Вас!
В частности, загружаю адресс.
Спасибо, ам.


> Спасибо Вам spv!
> Передо мной стоит задача именно, использую Ваши термины "...практических соображении, связанных с производством" такого рода. Список, приведенны мной есть не что иное, как перечисление выходов схемы. Выбор соответственно этих пар, обусловлен своими принципами.
>
> Задача состоит в том, что по возможности (при наличии) определить максимальный клик по данному списку.
>
> Например (на руках): cl=4 в подграфе, заданном парами : ut ts sx xu

> ut
> ts
> ( sx )
> xt
> cl=3 в подграфе, заданном парами : sr rp sp

>
> sr
> ( rp )
> pr

> и так далее.

>
> Провести сортировку.

> Полностью согласен, что по мощности вычисления порядка 10 в 3 (1024) - не проблема. Но предел есть. Главное в этом случае думаю, порядок величины "cl". Чем эта величина больше в конкретном списке, тем грубо говоря больше ..... хотя бы время.
> Мой вопрос был именно: есть ли такие готовые алгоритмы? Скрипты,кторые позволяют провести такую сортировку?
> В моем вооружении Perl. Начал было реализовывать, но уткнулся в проблему бесконечного числа циклов. Конечно понимаю, это зависит напрямую от уровня. Но все же. Есть ли они?

>
> С уважением , ал.


Не пробовали воспользоваться математическими пакетами? В Mathematica и Maple есть большие библиотеки по работе с графами, в частности, поиск наибольшей клики там присутствует.

А за теоретическим описанием алгоритмов сходите на http://elib.catalysis.nsk.su/elib/sci-lib/DjVu%20books%20edition/math_logic/catalog.html и скачайте там книгу Кристофидеса. Все нужное вам там, кажется, присутствует. А программирование алгоритма типа ветвей и границ не представляет труда.

Кстати, запрограммировать полный перебор можно и без бесконечного числа циклов.

http://elib.catalysis.nsk.su/elib/sci-lib/DjVu%20books%20edition/math_logic/catalog.html


приветы,

2 дня пытаюсь подобрать более-менее оптимальный алгоритм, вот задачка:

Нужно построить ориентированный граф с N вершинами, без петель, каждая вершина которого имеет минимум одну исходящую и одну входящую дугу. Причём из всех вариантов интересуют только неизоморфные графы. Используя бумагу и карандаш находим что для N=2 существует только 1 вариант - (01)(10) - (матрица смежности), для N=3 таких графов 5ть штук (011)(101)(110),(010)(001)(100),(010)(101)(010),(010)(101)(110),(010)(101)(100).
Для N=4 и 5 я смог подобрать на компьютере примитивным перебором элементов матрицы смежности. но для N=6 нужно 2^36-36 операций, что проблематично, и я начал поиск более оптимального алгоритма.
Может быть кто-нибудь сталкивался с таким или знает решение, буду благодарен за любую помощь



Пожалуйста, подскажите несчастной студентке, как пересчитать количество подграфов в графе с N вершинами и М ребрами? Заранее спасибо.


--------------------------------------------------------------------------------
Re: Количество подграфов
RElf
> Пожалуйста, подскажите несчастной студентке, как пересчитать количество подграфов в графе с N вершинами и М ребрами? Заранее спасибо.
Неточная формулирока. Рассмотрим два графа с вершинами a, b, c, d:

1) ребра (a,b), (a,c), (a,d)
посчитаем число подграфов:
с 0 ребер ~ 2^4=16
с 1 ребром ~ 3*2^2=12
с 2 ребрами ~ 3*2=6
с 3 ребрами ~ 1
всего 16+12+6+1=35

2) ребра (a,b), (b,c), (c,a), вершина d - изолированная
посчитаем число подграфов:
с 0 ребер ~ 2^4=16
с 1 ребром ~ 3*2^2=12
с 2 ребрами ~ 3*2=6
с 3 ребрами ~ 2
всего 16+12+6+2=36

Как видим, знания только N и M недостаточно, чтобы дать ответ на вопрос.


Есть програмка Lworks
Могу прислать (119 kb в rar-e)


Вот мои идеи, возникшие по поводу конструкции минимального остовного дерева графа. По поводу графа с ненаправленными связями я уверен на 99%(хотя, конечно мог где-то прогнать) а с направленными связями - только гипотезы. Возможно, я изобретаю велосипед, если кто знает - киньте, линк, пожалуйста.

Все дальнейшее раскрутилось из попытки формализации алгоритма Прима через матрицу связей.

Доказательство и формализация для случая ненаправленных связей прсото ДЕТСКОЕ: представляем узлы и связи как симметричную матрицу nxn(причем нас интересует только КУСОК ее над или под диагональю), и у оставшегося куска из каждого столбца выбираем минимальное значение - это и будут стоимсти связей MST а строка-столбец номера узлов.
Почему это верно? Для создания MST необходимо, чтобы каждый узел участвовал как минимум в одной связи - те в каждом столбце(или строке) нужно взять одно число в нашем случае - самое маленькое ненулевое и оно там БУДЕТ (матрица симметричная) если граф связный.
В случае графа с направленными связями все сложнее и тут я доказать пока ничего не могу но вроде должно быть так: строим матрицу (которая вообще говоря несимметричная и в которой могут быть СРАЗУ и нулевые столбцы и строки) и выбираем из нее n значений (минимальных в строках/столбцах причем для любого i нужно чтобы хотя бы 1 выбранное число стояло либов в i-m столбце либо строке) и пытаемся выкинуть одно (это не всегда возможно). Хотелось бы проверить (причем, желательно до завтрашнего утра) всегда ли это возможно и будет ли это MST
12 декабря 2003 г. 18:52


--------------------------------------------------------------------------------
Re: конструкция MST графов: охладите мой пыл!
kgb-woland
конечно, я прогнал... нужно смотреть и столбец, и строку
Контрпример:
021
203
130
12 декабря 20:41


Кто знает определение графа де Брейна, свойства, способы использовать, а также литературу на русском?
Из того, что нашел в Инете понятны только его некоторые черты:

http://www.beluch.newmail.ru/lifelex/lexr_g.htm
:граф де Брейна В применении к игре Жизнь, граф де Брейна - граф, показывающий, какие части могут быть связаны с какими другими частями, формируя верную часть образца Жизни специфического вида.

Например, если мы интересуемся натюрмортами, тогда мы могли бы рассмотреть прямоугольные части 2х3, а граф де Брейна показал бы, какие пары их могут перекрыться, чтобы сформировать квадрат 3х3, в котором центральная ячейка остается неизменной в следующем поколении.
22 марта 2004 г. 18:57:



> Кто знает определение графа де Брейна, свойства, способы использовать, а также литературу на русском?

На англиском в интернете полно ссылок. Искать "de bruijn graph".
Вот например: http://mathworld.wolfram.com/deBruijnGraph.html

Из русской литературы кое-что есть в книге Строки, деревья и последовательности в алгоритмах : Информатика и вычислительная биология


В одном учебнике "Лекции по теории графов", прочитал определение порожденного подграфа. При этом было дано определение подграфа порожденного множеством вершин и подграфа порожденного множеством ребер. Эти множества, которые порождают подграф включены в множества, соответсвенно вершин и ребер, исходного графа G.
1. Хотел спросить не одно ли это и тоже, граф порожденный множеством вершин и множеством ребер? Т.е. если взять некоторый подграф порожденный множеством вершин, то его так же можно назвать и графом порожденным множеством ребер, выделив при этом соответсвующие ребра.
2. Когда нам дается определение графа, то сразу задается некоторое непустое множество вершин V и некоторое множество E из множества всех его 2х элементых подмножеств(ребра). Допустим V=5, вершин в колличестве 5. Получается что мы уже интуитивно все вершины пронумеровали. Зачем вводить понятие нумерованного графа?
Или в нумерованном числа жестко связаны с вершинами, а обычный мы можем перенумеровать?
20 мая 2004 г. 11:02
--------------------------------------------------------------------------------

Re: Порожденный подграф.
Ираклий
В ответ на №11517: Порожденный подграф. от vl1985 , 20 мая 2004 г.:
> 1. Хотел спросить не одно ли это и тоже, граф порожденный множеством вершин и множеством ребер? Т.е. если взять некоторый подграф порожденный множеством вершин, то его так же можно назвать и графом порожденным множеством ребер, выделив при этом соответсвующие ребра.
Да, множество всех графов, которые пораждаются из данного с помощью вершин совпадает с множеством графов, которые пораждаются с помощью ребер. Просто в одних эадачах удобен один способ, в других - второй...

> 2. Когда нам дается определение графа, то сразу задается некоторое непустое множество вершин V и некоторое множество E из множества всех его 2х элементых подмножеств(ребра). Допустим V=5, вершин в колличестве 5. Получается что мы уже интуитивно все вершины пронумеровали. Зачем вводить понятие нумерованного графа?
> Или в нумерованном числа жестко связаны с вершинами, а обычный мы можем перенумеровать?

Конечно, один и тот же граф можно превратить в нумерованный вот каким количеством способов: |V|!
20 мая 14:10


Подскажите пожалуйста. Возникло недопонимание. Граф реконструируем, если он изоморфен каждой своей реконструкции. Вопрос такой: а как найти эти ВСЕ реконструкции, чтобы проверить что он каждой изоморфен и сделать вывод что он реконструируем. Просто в учебнике дается такое определение реконструкции графа G: что есть некий граф H, порядка такого же как и G, и существует такая нумерация графа H, при которой при постороении подграфов полученных в результате удаления вершин i => Gi~Hi, и это наблюдается для всех i. Ну а как узнать то все реконструкции...т.е. все их перебрать и сравнить с исходным на предмет изоморфности, в учебнике исходят из того что есть некий граф и он реконструкция .... потому то и потому то...
24 мая 2004 г. 15:15:



> Подскажите пожалуйста. Возникло недопонимание. Граф реконструируем, если он изоморфен каждой своей реконструкции. Вопрос такой: а как найти эти ВСЕ реконструкции, чтобы проверить что он каждой изоморфен и сделать вывод что он реконструируем. Просто в учебнике дается такое определение реконструкции графа G: что есть некий граф H, порядка такого же как и G, и существует такая нумерация графа H, при которой при постороении подграфов полученных в результате удаления вершин i => Gi~Hi, и это наблюдается для всех i. Ну а как узнать то все реконструкции...т.е. все их перебрать и сравнить с исходным на предмет изоморфности, в учебнике исходят из того что есть некий граф и он реконструкция .... потому то и потому то...
> 24 мая 2004 г. 15:15:


На самом деле имеется гипотеза Келли-Улама: каждый граф реконструируем. Гипотеза пока не доказана в общем случае. Так что если бы существовал какой-то внятный алгоритм перебора всех реконструкций заданного графа, то гипотезу Улама скорее всего бы уже доказали.

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

P.S. Каким учебником Вы пользуетесь?



> P.S. Каким учебником Вы пользуетесь?


Спасибо за ответ. Насчет учебника:
"Лекции по теории графов" сборных авторов:
Емеличев, Мельников, Сарванов, Тышкевич
Издательство Наука, Физматлит, 1990г. Но там про гипотезу Келли-Улама
упоминалось далее, я просто ее не доосмыслил. Ведь это всего лишь гиппотеза а не теорема.


> P.S. Каким учебником Вы пользуетесь?

А не подскажете еще вот момент. Число ребер n-мерного куба Gn дается как очевидное и равное n*2^n-1. Исходя из того что каждая вершина инциндента 3м ребрам. То что порядок равен 2^n - понятно. Вершины представлены n-мерными векторами длины 1 и смежны только в том случае когда различаются только в одной координате тоже понятно. А как подсчитали число ребер не вижу. Откройте мне глаза. Можно выписать все вершины, но как дальше считать..



> А не подскажете еще вот момент. Число ребер n-мерного куба Gn дается как очевидное и равное n*2^n-1. Исходя из того что каждая вершина инциндента 3м ребрам. То что порядок равен 2^n - понятно. Вершины представлены n-мерными векторами длины 1 и смежны только в том случае когда различаются только в одной координате тоже понятно. А как подсчитали число ребер не вижу. Откройте мне глаза. Можно выписать все вершины, но как дальше считать..

Описка, каждая вершина инцидентна n-ребрам.


>
> > А не подскажете еще вот момент. Число ребер n-мерного куба Gn дается как очевидное и равное n*2^n-1. Исходя из того что каждая вершина инциндента 3м ребрам. То что порядок равен 2^n - понятно. Вершины представлены n-мерными векторами длины 1 и смежны только в том случае когда различаются только в одной координате тоже понятно. А как подсчитали число ребер не вижу. Откройте мне глаза. Можно выписать все вершины, но как дальше считать..

> Описка, каждая вершина инцидентна n-ребрам.

По лемме о рукопожатиях. Удвоенное число ребер равно сумме степеней вершин.


Помогите пожалуйста кто нибудь разобраться с доказательством.
Теорема: если число компонетн k(G)=k для n-вершинного графа G,
то
n-k<=m(G)<=(n-k)*(n-k+1)/2
где m(G) - число ребер этого графа,
причем обе оценки для m(G) достижимы.
Доказательство второй части понятно.
А доказательство первой части, т.е. m(G)>=n-k не совсем понятно.
В учебнике доказывается по индукции. Привожу пример:
Неравенство очевидно когда m(G)=0, т.к. тогда k=n. Воспользуемся индукцией по
m(G). Пусть m(G)>0 и пусть для графов с меньшим, чем m(G), числом ребер соответствующее неравенство верно... Вот тут и уже становится непонятно, мы вроде бы предполагаем то, что еще только нужно доказать... разве не так?
Дальше... Рассматривается граф G-e, где e - ребро, которое принадлежит G.
Согласно некоторой лемме 1 (лемма 1 см. ниже), число компонент этого графа равно k или k+1. Число ребер в нем равно m(G)-1. По индуктивному предположению в обоих случаях m(G)-1>=n-k-1. Следовательно m(G)>=n-k.
Непонятно как мы можем предполагать то, что еще только нужно доказать....???
Ниже привел лемму..., на которое опирается док-во.

Лемма 1: Пусть G-связный граф, e принадлежит множеству ребер графа G.
1. Если ребро e принадлежит какому либо циклу графа G, то граф G-e - связан.
2. Если ребро e не входит ни в какой цикл, то граф G-e имеет ровно 2 компоненты.
03 июня 2004 г. 12:29


Каково ожидаемое кол-во вершин степени k в случ. графе порядка n?
17 октября 2004 г. 21:20:


> Каково ожидаемое кол-во вершин степени k в случ. графе порядка n?

n C(n-1,k) p^k (1-p)^(n-1-k),

где p - вероятность наличия каждого из ребер графа.


> > Каково ожидаемое кол-во вершин степени k в случ. графе порядка n?

> n C(n-1,k) p^k (1-p)^(n-1-k),

> где p - вероятность наличия каждого из ребер графа.

Большое спасибо. А не подскажете ли где в ин-те посмотреть инф-ю об ожидаемых знач-х инвариантов графов и т.п. ?


Помогите, пожалуйста, решить две задачки или найти их решение.
1) Доказать, что при каждом целом n>=1 существует такой граф Gn порядка n, что только две вершины имеют одинаковую степень.
2) Доказать, что граф Gn является единственным с точностью до изоморфизма.
21 октября 2004 г. 17:20:


> Помогите, пожалуйста, решить две задачки или найти их решение.
> 1) Доказать, что при каждом целом n>=1 существует такой граф Gn порядка n, что только две вершины имеют одинаковую степень.
> 2) Доказать, что граф Gn является единственным с точностью до изоморфизма.

Наверное, речь идет о связанных графах; в противном случае контр-пример к утверждению 2: графы на двух вершинах, в котором есть ребро и в котором нет ребра соединяющего вершины, не являются изоморфными.

Для связанных графов обе задачи решаются по индукции:

Граф на двух вершинах соединенных ребром, очевидно, является единственным (с точностью до изоморфизма) графом на n=2 вершинах, удовлетворяющим условию 1.

1) Пусть есть связанный граф на n вершинах, в котором только две вершины имеют одинаковую степень. Пусть эти две вершины u и v, и их степень равна d. Заметим, что d < n-1, так как в противном случае в графе не будет вершин степени 1, а значит найдется еще одна пара с равными степенями.
Добавим к графу новую (n+1)-ю вершину, которую мы соединим со всеми вершинами степени > d и с вершиной u. Легко видеть, что все n вершин исходного графа будут иметь попарно различные степени в новом графе, а добавленная вершина будет иметь степень совпадающую со степенью какой-то из прежних вершин.

2) Пусть утверждение справедливо для графов на <= n вершинах. Рассмотрим два графа на n+1 вершинах, удовлетворяющие условию 1. Тогда в этих графах найдуются вершины имеющие степень n, причем такие вершины единственны. Поставим эти вершины друг другу в соответствие, и выкинем их из графов вместе со всеми инцидентными ребрами. Тогда останутся графы на n вершинах, по-прежнему удовлетворяющие условию 1. По предположению индукции они изоморфны, значит изоморфны и исходные графы.


> Помогите, пожалуйста, решить две задачки или найти их решение.
> 1) Доказать, что при каждом целом n>=1 существует такой граф Gn порядка n, что только две вершины имеют одинаковую степень.
> 2) Доказать, что граф Gn является единственным с точностью до изоморфизма.
> 21 октября 2004 г. 17:20:

Если нужно, могу прислать подробное решение (с картинками) письмом. Долго рисовал картинки. В целом решение мало отличается от решения RElf. Могу лишь добавить, что пара вершин с одинаковыми степенями в Gn имеют степень d=[n/2].


Здравствуйте.
Подскажите, пожалуйста, ссылки на ресурсы с информацией по общей теорией графов. Желательно по-популярнее.
Задача у меня вот какая - необходимо оптимизировать работу предприятия. Есть структурные подразделения, так понимаю - вершины, и какие-то взаимосвязи между ними, так понимаю - ребра. Можно ли рассматривать организацию с точки зрения теории графов? Если да, то что тут можно оптимизировать? Может, кто-нибудь знает, где есть хорошие ресурсы с информацией в данном контексте - приложения теории графов к конкретным задачам оптимизации бизнес-процессов? Сам я, честно говоря, в графах не очень, однако меня заинтересовал данный вопрос в рамках моей деятельности - внедрения корпоротивной информ. системы. При такой постановке задачи для упрощения внедрения КИС, имеет смысл упростить работу организации.
Если не трудно, ответьте на qwe32[собака]nm[точка]ru.


Пожалуста!!!!!Подскажите, где можно найти программу, реализующую Алгоритм направленного древовидного поиска медианы в графе.


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


здравствуйте.пожалуйста подскажите алгоритм нахождения точек сочленения для неориентированного графа(такие точки,удалив которые граф распадается на два или более).знаю, это (как один из способов) можно реализовать путём "поиска в глубину"
буду очень признателен за любую помощь: ссылки,текст программы,блок схема,обьяснения на словах,примеру, всему
зарание спасибо.
04 декабря 2004 г. 21:08:


> здравствуйте,помогите пожалуйста с решением задачи: алгоритм нахождения точек сочления в неориентированном графе

Возьми алгоритм установления числа компонент связности,
подставляй в него матрицу смежности, вычеркивая строку и столбец соответствующий i-той точке,
если число комп связности увеличилось -это точка сочленения, нет-нет :-)


Здравствуйте!
Есть некий граф, состоящий из 1 или более подграфов, каждый из которых связан, в то время как сам граф может быть несвязан. Требуется выявитиь в данном графе все связанные подграфы. Буду благодарен если кто-нибудь укажет на быстрый алгоритм.
ФД
09 февраля 2005 г. 14:13:



Ребята, спасибо всем за помощь. Особенно sceptic и RElf, вы мне здорово помогли в прошлый раз!

Сейчас мне снова требуется помощь. Помогите, пожалуйста, решить их или найти решение:)

1. Доказать, что в вершинно трехсвязном графе любые три вершины лежат на общем простом цикле. (Указание: воспользоваться теоремой Уитни)

2. Дан граф G(V,E) без изолированных вершин и такая функция f: V->[0,1], что f(u)+f(v)<=1 для любого ребра uv из E. Доказать, что сумма(по v из V) f(v) <=b1(G). Где b1(G) - число реберного покрытия G. (Указание: использовать строение подграфа, образованного мин. реберным покрытием G)

3. Доказать, что множество ребер любого реберно-двусвязного кубического графа можно разбить на непересекающиеся простые цепи длины 3. (Указание: воспользоваться теоремой Петерсена)
29 марта 2005 г. 12:43:


Привет!
Случилась проблема-для простой по сути задачи не хватило немного(или много) мозгов.
Задача касается теории расписаний

Есть ациклический граф, на нем изображены работы с директивным сроком.

Рассматривается максимальная вершина в ациклическом графе, директивный срок которой максимален.

Нужно доказать утверждение что: Допустимое расписание существует тогда и только тогда когда существует расписание где данная максимальная работа исполняется последней.

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

Спасибо:)
17 мая 2005 г. 03:06:


Объясните, пожалуйста, мне алгоритм определения изоморфности графов.
06 сентября 2005 г. 17:07



Господа, есть проблема, точнее есть необходимость знать алгоритм сечения графа собственным векторм.
Исхлдные данные:
Весовые коэффициенты графа — матрица W(NXN)
собственный вектор этой матрицы.
Необходимо провести чечение графа с помощью собственного вектора. проблема заключается как я понимаю в выборе начальной точки сечения и собственно алгоритме сечения.
02 ноября 2005 г. 11:28:


Народ помогите составить алгортм решения следующей задачки:
Найти все максимальные изоморфные пересечения по подграфам двух графов из семейства двудольных.
не откажусь от любой помощи(литература ссылки готовые решения)


появилась надобность написать программу для Определения наименьшего доминирующего множества в графе. а именно размещение военных баз. изобретать велосипед на хочется, если у кого нить есть код готовый выложите или пришлите плиз. в принцепе язык не важен, но желательно бы на дельфях или на с++...
за ранее спасибо)


Присвоить всем рёбрам вес 1. Исходя из алгоритма нахождения максимального потока, найти минимальный разрез (искомое множество рёбер)


То, что написано вначале и в конце не одно и то же.
Если в графе есть хотя бы 2 ребра -> их можно считать двумя путями и не через какое ребро эти два путя не проходят однлвременно -> такого ребра, через которого проходят все пути, нет.
А для первого варианта:
Если граф дерево - то все рёбра
Если есть циклы, то берём любой цикл, а точнее его вершины. "Стягиваем" их в одну вершину, а рёбра, идущие в "стягиваемые" вершины, заменяем на рёбра ,идущие в новую вершину. И так действуем пока не получим дерево -> оставшиеся рёбра и есть искомые.


Здравствуйте. У меня вопрос по определению накрытия графа. В определении говорится, что морфизм графов F:X-Y является накрытием если звезда любой вершины v Е X , биективно отображается на звезду вершины f(v). Однако в X и Y может быть разное количество вершин и биекции не получается. Объясните, что я не понял. Заранее благодарен.
22 февраля 2006 г. 18:49:



Всем привет!
на днях дали тему диплома "разработка модели транспортной задачи как комбинаторной и методы её решения"
Сразу говорю, что под этим скрываеться!
1. транспортная задача
2. 3 целевых функции
3. ограничения
4. ограничения многогранника

вообщем я попал! графы, комбинаторика - что делать я не знаю! ни литературы ничего вообще нету! немного в инете нарыл, но но но!
Люди кто может сталкивался с этим, - помогите пожалуйста! если что пишите на sirius128@rambler.ru ICQ 316712091 ЗАрание ВАМ благодарен!
06 апреля 2006 г. 18:23:


> Объясните, пожалуйста, мне алгоритм определения изоморфности графов.
> 06 сентября 2005 г. 17:07



А Вам алгоритм планарности графа ничем помочь не может? Если может, то пишите.


18052: Топология и графы Mick-R 25 мая 13:04
В большинстве математической литературы топология на графах рассматривается как нечто самоочевидное. Подскажите пожалуйста как задается топология на графах - что является открытым множеством, как выполняется аксиоматика. Очень буду благодарен за ссылку на электронную книгу.


Люди ХЕЛП, дали контрольную ПО ГРАФАМ - Ужас...Ничего не объяснили(ну я думаю знаете как преподают сейчас) По теории графов, ПЛИЗ кто может помочь решить отпишитесь на почту. ОЧЕНЬ ПРОШУ!!!!!!!!!!!!!!!!
sergeyandvitas@km.ru


Где можно найти доказательства того, что самодополнительный граф имеет диаметр от 2 до 3, что он связен и что количество вершин = 0,1mod4?
11 июня 2006 г. 10:41:


> Где можно найти доказательства того, что самодополнительный граф имеет диаметр от 2 до 3, что он связен и что количество вершин = 0,1mod4?
> 11 июня 2006 г. 10:41:

Связность и нижнию оценку 2 на диаметр очень легко доказать (рассказать?). Остальное я не знаю.


> количество вершин = 0,1mod4?

Ой, это тоже безумно очевидно! (MariS, are you here?)


> Где можно найти доказательства того, что самодополнительный граф имеет диаметр от 2 до 3, что он связен и что количество вершин = 0,1mod4?
> 11 июня 2006 г. 10:41:

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


> Объясните, пожалуйста, мне алгоритм определения изоморфности графов.
> 06 сентября 2005 г. 17:07
Изоморфность графов - означает, что графы одинаковые с точностью до нумерации вершин, т.е. если один из них "покрутить", не разрывая ребер, то получится второй.
Алгоритмов куча, но задача является NP-полной, т.е. не существует алгоритмов, заканчиваемых за полиномиальное время. Если это не волнует, то простой перебор:
1. Берем первую попавшуюся пару вершин из обоих графов
2. Проверяем по кол-ву исходящих ребер. Если совпадает, запоминаем и переходим к п.1 (например, по рекурсии). Если не совпадает, переходим к п.1 просто так, не запоминая.
3. Если все вершины уже использованы, то графы изоморфны. Если не все, то не изоморфны.

Понятно, или накалякать на PigeonPascal?


Существует более 25 доказательств формулы Кэли для количества полных деревьев в полном графе. Эту формулу несложно найти и обосновать по индукции. Но ввиду важности результата интересно узнать есть ли простое, комбинаторное, неиндуктивное доказательство? Что-нибудь наподобии вывода формулы кол-ва размещений без поторений и т.п.


> Существует более 25 доказательств формулы Кэли для количества полных деревьев в полном графе. Эту формулу несложно найти и обосновать по индукции. Но ввиду важности результата интересно узнать есть ли простое, комбинаторное, неиндуктивное доказательство?

См. проблему 26 в книге:

Proofs from THE BOOK


> Объясните, пожалуйста, мне алгоритм определения изоморфности графов.
> 06 сентября 2005 г. 17:07


:) изоморфизм графов... по сути дела тема очень интересная и понятная, но с точки зрения программирования это очень не легко:(
у меня есть кое какая инфа по этому поводу:)

если интересно, то мой адрес tamirlana007@rambler.ru


Вопрос, в принципе тот же: нужен точный алгоритм для нахождения изоморфизма(по типу алгоритма Прима-Краскала для минимального дерева), если у кого есть теория на этот счет, выложите, буду благодарен, либо ссылки на соотв. материал. ;)



Представляю Вашему вниманию следующую задачу:

Доказать, что граф G связный, тогда и только тогда, когда для любого разбиения V=(V1,V2) ,при V1 и V2 не равны нулю, существует ребро, соединяющее вершину из V1 c V2.

Вроде ничего такого, тем не менее не могу сообразить. :)
Подскажите пожалуйста идею решения.
25 декабря 2006 г. 08:22:


> Здравствуйте. У меня вопрос по определению накрытия графа. В определении говорится, что морфизм графов F:X-Y является накрытием если звезда любой вершины v Е X , биективно отображается на звезду вершины f(v). Однако в X и Y может быть разное количество вершин и биекции не получается. Объясните, что я не понял. Заранее благодарен. > 22 февраля 2006 г. 18:49:


Помогите пожалуйста решить,если кто может.Очень надо!!!
По матирце пропускных способностей дуги ориентированного графа найти максимальный поток от вершины S=x1 , a t=x7.
Матрица пропускных способностей для заданного графа:
x1 x2 x3 x4 x5 x6 x7

x1 - 5 11 - - 25 -

x2 - - - - 14 - 29

x3 - - - 3 - 16 -

x4 - - - - - - 6

x5 - - - 17 - - -

x6 - - - - 8 - 4

x7 - - - - - - -


Помогите, пожалуйста, решить задачу:

Докажите, что если число ребер графа порядка n>2 больше, чем (n-1)(n-2)/2, то граф cвязен.


Помогите, пожалуйста, решить задачу:

Определить число ребер n-мерного куба.


> Помогите, пожалуйста, решить задачу:

> Определить число ребер n-мерного куба.

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

Если понять то, что написано выше, то становится очевидным, что число вершин n-мерного куба равно , а число ребер, имеющих общую вершину, равно . Отсюда следует, что число ребер n-мерного куба равно (поскольку одно ребро является общим для двух вершин).


> ... число вершин n-мерного куба равно , а число ребер, имеющих общую вершину, равно . Отсюда следует, что число ребер n-мерного куба равно (поскольку одно ребро является общим для двух вершин).

Правильно будет:

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


> Докажите, что если число ребер графа порядка n>2 больше, чем (n-1)(n-2)/2, то граф cвязен.

Доказательство от противного. Предположим, что граф несвязный. Тогда его можно разбить на два непустых подграфа так, что в исходном графе нет ребер ведущих из одно подграфа в другой. Пусть m - это число вершин в первом подграфе, где 1<=m<=n-1, тогда во втором подграфе n-m вершин. Максимальное суммарное число ребер в этих подграфах (достигается в случае, когда оба подграфа являются полными графами) равно
m*(m-1)/2 + (n-m)*(n-m-1)/2 = m^2 - n*m + (n^2 - n)/2.
Максимум этой функции достигается на границе интервала значений m, то есть при m=1 или m=n-1, и равен (n^2 - 3n + 2)/2 = (n-1)(n-2)/2.
Таким образом, если в нашем графе хотя бы на одно ребро больше, то он обязан быть связным.


Люди помогите решить задачу. Условие:
Есть план местности. На нем отмеченны города и ж/д пути между ними. Есть старинная карта тойже местности. На ней отмеченны торговые пути мемжду городами.
Необходимо найти максимальное согласование старых и новых путей. Задача n-p полная. Хотелося бы увмдеть код алгоритма.


> Где можно найти доказательства того, что самодополнительный граф имеет диаметр от 2 до 3, что он связен и что количество вершин = 0,1mod4?
> 11 июня 2006 г. 10:41:


Здравствуйте, коллеги! Скажите, есть ли какая-нибудь теория или область олимпиадной математики, которая изучала бы такие графы:

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

Мне интересно узнать, какие графы тут могут получаться.


> Задана конечная система отрезков (другие варианты: лучей, промежутков) на прямой. Они есть вершины графа. Две вершины соединяются, если отрезки пересекаются (другие варианты: не пересекаются, находятся в заданном расположении друг относительно друга).

Это т.н. интервальный граф (interval graph). Про них много чего известно.
Знакомство можно начать отсюда:
http://en.wikipedia.org/wiki/Interval_graph
http://mathworld.wolfram.com/IntervalGraph.html
ну или погуглите.

Interval graph @ wikipedia


> Это т.н. интервальный граф (interval graph). Про них много чего известно.
> Знакомство можно начать отсюда:
> http://en.wikipedia.org/wiki/Interval_graph
> http://mathworld.wolfram.com/IntervalGraph.html
> ну или погуглите.

О, здорово, спасибо!


Методика поиска маршрута в связном графе
Добрый день всем. Буду очень признателен, если кто-нибудь подскажет методы решения следующей задачи (либо хотя бы определит направление в котором надо двигаться для ее решения ):

Есть связный математический граф из N вершин. Число N может быть сколь угодно большое.
Вес любого ребра в графе равен одному и тому же числу (Т.е. можно сказать, что граф не является взвешенным).

Каждому узлу графа может быть сопоставлено любое значение X (например, методом координат любой размерности и любого формата записи).
Каждый узел знает только свое значение Х, а так же значения Х соседних узлов (т.е. узлов соединенных с ним ребрами). Значения X остальных узлов ему неизвестны. Так же как не известна матрица смежности графа.

Введем следующее понятие: "сообщение узлу Б". Каждое сообщение хранит значение Х узла Б. Сообщения могут передаваться только между узлами соединенными ребрами.

Необходимо решить следующую задачу:
Даны два узла А и Б, которые не имеют общего ребра. Разумеется, между А и Б всегда есть кратчайший маршрут соответсвующий наименьшему количеству узлов, через которые этот маршрут проходит. Узлу А поступило задание передать сообщение узлу Б. Однако узел А может передать сообщение только кому-то из своих соседей. Разумеется, узел А знает как значение Х узла Б (оно хранится в сообщении), так и значения Х своих соседей. Необходимо описать метрику выбора соседа узла А, которому последний должен передать сообщение. Этой же метрикой воспользуется сосед узла А, чтобы определить куда дальше отправить сообщение. И так до тех пор, пока сообщение не достигнет узла Б.

Необходимо так изначально определить числа Х для всех узлов графа, а так же "метрику выбора соседа", чтобы гарантировать, что для любой вершины А возможно будет всегда доставить сообщение узлу Б по кратчайшему маршруту (или по маршруту близкому к кратчайшему).


Дан плоский кубический граф (степень каждой вершины = 3). Сказано, что каждая грань имеет не менее 5 вершин. Необходимо показать, что граф имеет не менее 12 вершин.


все привет, помогите пожалуйста.
Задание:
дан цикличный граф с разными весами дуг, нужно найти такую точку из которой диаметр будет минимальным.
здесь точка иметься ввиду что на ребре весом 10 будет 10 точек, надеюсь понятно объяснил.
но существует доказанная теория решения этой задачи.
нужно найти середину максимального ребра и найти противоположную точку(т.е. на другом конце ребра), это и будет искомой точкой.
а вот что я не могу сделать:
я задаю в таблице вершины(1; 2; 3; 4...n), ребра(1,2; 2,3; 3,4.... n,1) и
вес ребер (10; 5; 2.....)
и я не знаю как мне хронить в каком ребре я нахожусь, когда я буду идти до противоположной точки и как мне сделать что бы цикл переходил в последние ребра в первое


Физика в анимациях - Купить диск - Тесты по физике - Графики on-line

Реклама:
Rambler's Top100