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

Question

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

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

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

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

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

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

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

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

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.

Максимальное значение пх - х^2, х = (п/2)

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

Answer 2

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

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

В качестве альтернативы это можно сделать также с помощью DFS. Подход остается тем же.

Answer 3

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

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

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

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

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

Однако это можно взять разрез таким образом, что пропускная способность разреза больше разреза емкости минимальной S-т сети. Вы не думаете, что это значит? Например, в example at the top of this article, если вы перерезали между s и остальной частью сети, емкость разреза больше минимальной пропускной способности s-t сети.

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

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

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

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

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

Vertex cover графа представляет собой набор вершин таким образом, что каждое ребро графа падает, по меньшей мере, одна вершина множества.

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

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