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

Question

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

Правдивые или ложные вопросы

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

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

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

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

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

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

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

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

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

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

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

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

Answer 1

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

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

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

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

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

Answer 2

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

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

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

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

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

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

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

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

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

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

2) Я согласен с @glebm, что вы ошиблись ... извините.« Оболочка вершины графа - это множество вершин», но вы, кажется, написали список ребер?сопровождаемый списком одноэлементных наборов вершин?

Покрытие вершины графа - это множество вершин, так что каждое ребро графа инцидентно по крайней мере одной вершинемножество.

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

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

Answer 3

Graph Connectivity:

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

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