Вопросы по теории графов из моей сегодняшней викторины по алгоритмам, которые я хотел бы помочь понять

Сегодня у меня была викторина по алгоритмам за семестр, и я не могу понять эти два вопроса, и они беспокоили меня весь день. Я просмотрел свои заметки и конспекты лекций, и я все еще не уверен. Я был бы признателен, если бы кто-то мог взглянуть и дать некоторое представление об этих вопросах. Это не домашнее задание, а я уже сдала викторину.

Верные или ложные вопросы

1) [Перефразировано] Максимальное количество ребер в двудольном графе с n вершинами равно n(n-1)/2.

Я поставил это как False, моя логика такова, что n вершин означает, что у нас есть две n/2 строки. Первый узел имеет n/2 соединения со второй строкой, второй ряд имеет n/2 соединения со второй строкой... и т.д...

Следовательно, я рассчитал, что максимальное количество ребер в двудольном графе с n вершинами равно (n ^ 2/4).

2) [Перефразировано] Можно ли выбрать разрез, который не обязательно является минимальным разрезом s-t в графе с направленными потоками (алгоритм Форда-Фалкерсона), такой, что пропускная способность больше, чем пропускная способность разреза s-t?

Ставлю false, но не понимаю вопроса... Можно ли взять с-т разрез такой, чтобы пропускная способность была больше? Я знаю теорему слабой двойственности и «максимальный поток = минимальный разрез», поэтому я написал «ложно», но понятия не имею.

Краткий ответ на вопрос:

1) Объясните эффективный способ проверки погоды на графе.

Я предложил сделать поиск в ширину и если в графе были узлы, не найденные алгоритмом BFS, то он не был связан. Я записал, что время выполнения было O(m+n), следовательно, это был эффективный алгоритм для использования. Это стоило двух баллов, и это был последний вопрос, но теперь я беспокоюсь, что это был вопрос с подвохом.

2) На графике:

альтернативный текст

Перечислите наборы вершин, которые демонстрируют минимальное вершинное покрытие [перефразировано]

Мой ответ был {A, D}, {A, E}, {B, C}, {B, D}, {C, E}, но теперь я беспокоюсь, что это было просто {A}, {B}, {С}, {D}, {Е}...

Спасибо, что нашли время прочитать! :)


graph algorithm math theory
person gurk    schedule 13.10.2010    source источник
comment
Ну, ты испортил последнее.   -  person glebm    schedule 13.10.2010
comment
Да, я понял это уже после того, как вернулся домой...   -  person gurk    schedule 13.10.2010
comment
Вы могли бы получить некоторые лучшие ответы на mathoverflow.com.   -  person Jacob    schedule 13.10.2010
comment
Что такое двудольный граф? en.wikipedia.org/wiki/Bipartite_graph не говорит, что два набора узлов должны иметь одинаковое количество элементов ... так что один набор может быть просто пустым, это тоже двудольный граф?   -  person sandris    schedule 13.10.2010
comment
@Jacob: Маловероятно. Если вы не считаете, что вопрос, закрытый в течение нескольких секунд, является лучшим ответом.   -  person sepp2k    schedule 13.10.2010
comment
@sandris: правда, но это не повлияет на максимальное количество ребер. Скорее это даст минимальное число (ноль).   -  person LarsH    schedule 18.10.2010
comment
@gurk Я записал, что время работы было O (m + n), поэтому это был эффективный алгоритм. Что такое м и н? Вопрос о связности относился к двудольным графам?   -  person LarsH    schedule 18.10.2010
comment
@LarsH: Ах, действительно, спасибо :-)   -  person sandris    schedule 19.10.2010

Ответы (3)


arrow_upward
1
arrow_downward

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

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

Тогда максимальное количество ребер в этом графе будет x(n-x) или nx - x^2.

Максимальное значение nx - x^2 равно x = (n/2)

Таким образом, максимальное количество ребер в графе равно (n/2) * (n - (n/2)) = (n ^ 2)/4, как вы указали.

person Kirk Broadhurst    schedule 13.10.2010
comment
Я согласен, хотя мне интересно, следует ли предусмотреть случай, когда n нечетно. Однако это был всего лишь вопрос «Верно/Неверно», а правильный ответ явно неверен. - person LarsH; 18.10.2010

arrow_upward
0
arrow_downward

График подключения:

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

Кроме того, это также можно сделать с помощью DFS. Подход остается прежним.

person Chander Shivdasani    schedule 13.10.2010

arrow_upward
0
arrow_downward

1) был дан ответ, и я согласен, что вы были правы.

2): вопрос кажется двусмысленным, как указано.

such that the flow capacity is greater than the s-t cut capacity

пропускная способность чего? всей сети? или из разреза?

Если последнее, то, кажется, спрашивается, может ли А > А, что явно неверно. Если первое, то снова ясно, что ответ неверен. Если бы можно было найти такой разрез, то max-flow=min-cut не был бы верным: максимальный поток сети был бы больше, чем минимальная пропускная способность разреза s-t.

Однако можно выбрать разрез таким образом, чтобы пропускная способность разреза превышала минимальную пропускную способность разреза s-t сети. Вы не думаю, что это то, что они имели в виду? Например, в примере вверху этой статьи, если вы перережете s и остальные сети пропускная способность разреза больше, чем минимальная пропускная способность s-t разреза сети.

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

Может быть, это поможет увидеть точную оригинальную формулировку.

Короткий ответ:

1) был дан ответ, хотя я не понимаю, что такое m (в O (m + n)), если только вы не говорите о двудольном графе?

2) Я согласен с @glebm, что вы ошиблись... извините. "Покрытие вершин графа — это набор вершин", но вы, кажется, написали список ребер? за которым следует список одноэлементных наборов вершин?

Вершинное покрытие графа – это набор вершин, которому каждое ребро инцидентно хотя бы одна вершина множества.

Поскольку это полный граф, все вершины взаимозаменяемы. Таким образом, нам все равно, какие вершины, а только сколько вершин нам нужно, чтобы коснуться всех ребер. Ответ найти нетрудно. Если мы выберем любые три вершины, ребро, соединяющее две другие вершины, не будет «покрыто». КЭД.

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

person LarsH    schedule 19.10.2010