Доступ к сервису временно запрещён
С вашего IP-адреса одновременно поступает очень много запросов.
Такое поведение показалось подозрительным, поэтому мы временно закрыли доступ к сайту.
Возможно, на вашем устройстве есть программы, которые отправляют запросы без вашего ведома.
Что мне делать?
Напишите в службу поддержки через форму обратной связи.
Подробно опишите ситуацию — поможем разобраться, что случилось, и подскажем, как действовать дальше.
В однородном графе 12 вершин. Степень каждой вершины равна 5. Сколько рёбер в этом графе?
Сумма степеней вершин графа равна удвоенному числу его рёбер.
MR_WollyУченик (112) 1 год назад
Max MerkulovУченик (103) 1 год назад
Можно еще зануднее написать?
Кто занудствует, так это ты
Остальные ответы
Требуется количество вершин умножить на степень вершин, что будет равно удвоенному количеству ребер —> надо будет еще на два разделить :
12*5=60
60:2=30
Ответ: 30 ребер
Похожие вопросы
Ваш браузер устарел
Мы постоянно добавляем новый функционал в основной интерфейс проекта. К сожалению, старые браузеры не в состоянии качественно работать с современными программными продуктами. Для корректной работы используйте последние версии браузеров Chrome, Mozilla Firefox, Opera, Microsoft Edge или установите браузер Atom.
Сколько ребер в этом графе
Построй граф, вершинами которого будут числа 3,4,5,8,12,25,140
и две вершины связаны ребром только в том случае, если одно из чисел делится на другое без остатка. Сколько рёбер в этом графе?
Лучший ответ
Остальные ответы
6 ребер
140 — 4
140 — 5
25 — 5
12 — 4
12 — 3
8 — 4
Айтана ТекушеваУченик (125) 1 месяц назад
Всë верно! Спасибо)
Наталья МироноваУченик (113) 2 недели назад
Похожие вопросы
Ваш браузер устарел
Мы постоянно добавляем новый функционал в основной интерфейс проекта. К сожалению, старые браузеры не в состоянии качественно работать с современными программными продуктами. Для корректной работы используйте последние версии браузеров Chrome, Mozilla Firefox, Opera, Microsoft Edge или установите браузер Atom.
Вершинная, рёберная связность, связь между ними и минимальной степенью вершины
Связь между вершинной, реберной связностью и минимальной степенью вершины
Пускай минимальная степень вершины графа [math]G[/math] обозначается буквой [math]\delta[/math] . Тогда:
Для любого графа [math]G[/math] справедливо следующее неравенство: [math]\kappa \leqslant \lambda \leqslant \delta [/math]
Полный граф. [math] \lambda = \delta = \kappa = 4[/math]
Для любых натуральных чисел [math]a, b, c[/math] , таких что [math]a \leqslant b \leqslant c[/math] , существует граф [math]G[/math] , у которого [math]\kappa = a, \lambda = b[/math] и [math]\delta = c [/math]
Граф, в котором [math] \delta = 4[/math] , [math]\lambda = 3[/math] , [math]\kappa = 2[/math] .
Рассмотрим граф [math]G[/math] , являющийся объединением двух полных графов [math]G_1[/math] и [math]G_2[/math] , содержащих [math]c + 1[/math] вершину. Отметим [math]b[/math] вершин, принадлежащих подграфу [math]G_1[/math] и [math]a[/math] вершин, принадлежащих подграфу [math]G_2[/math] . Добавим в граф [math]G[/math] [math]b[/math] ребер так, чтобы каждое ребро было инцидентно помеченной вершине, лежащей в подграфе [math]G_1[/math] и помеченной вершине, лежащей в подграфе [math]G_2[/math] , причем не осталось ни одной помеченной вершины, у которой не появилось хотя бы одно новое ребро, инцидентное ей. Тогда:
Нахождение реберной связности
Для нахождения реберной связности нужно перебрать все пары вершин [math]s[/math] и [math]t[/math] , найти количество непересекающихся путей из [math]s[/math] в [math]t[/math] и выбрать минимум. Пусть он равен [math]l[/math] . По утверждению, граф является [math]l[/math] -связным, причем такое [math]l[/math] — максимально (ведь мы явно нашли количество путей). А значит, по определению, реберная связность равна [math]l[/math] .
Для нахождения количества непересекающихся путей из [math]s[/math] в [math]t[/math] воспользуемся алгоритмом нахождения максимального потока. Сопоставим каждому ребру пропускную способность, равную [math]1[/math] и найдем максимальный поток (например, алгоритм Эдмондса-Карпа). Он и будет равен количеству путей. Действительно, если провести декомпозицию потока, то получим набор реберно непересекающихся путей из [math]s[/math] в [math]t[/math] , по которым поток неотрицателен и равен [math]1[/math] (т.к. пропускная способность всех ребер равна [math]1[/math] ). А значит, если поток равен [math]flow[/math] , то и количество путей равно [math]flow[/math] .
Псевдокод алгоритма
function disjoint_paths_count(): int ans = INF for for flow = find_max_flow(s, t) // максимальный поток — количество путей из в ans = min(ans, flow) return ans
Оценка работы
Время работы равно [math]V^2 \times O(find\_max\_flow)[/math] . При использовании алгоритма Эдмондса-Карпа время равно [math]V^2 \times O(V E^2)[/math] или [math]O(V^3 E^2)[/math]
Нахождение вершинной связности
Используя аналогичные утверждения и определения для вершинной связности придем к такому же алгоритму с тем отличием, что понадобится искать вершинно-непересекающиеся пути. Искать их можно тем же способом, если сопоставить каждой вершине пропускную способность, равную [math]1[/math] . Для этого воспользуемся известным трюком:
Разобьем каждую вершину [math]v[/math] графа на две вершины [math]v_1[/math] и [math]v_2[/math] . Все ребра, которые входили в [math]v[/math] будут входить в [math]v_1[/math] . Все ребра, которые выходили из [math]v[/math] будут выходить из [math]v_2[/math] . Так же добавим ребро [math](v_1, v_2)[/math] с пропускной способностью [math]1[/math] .
Иллюстрация
После этого для нахождения количества вершинно непересекающихся путей в исходном графе будем искать количество реберно непересекающихся в новом графе.
Тем самым сведя задачу к нахождению реберной связности.
См. также
- Теорема Менгера
- Алгоритм Эдмондса-Карпа
- Википедия — Теорема Роббинса
Источники информации
- Харари Ф. Теория графов: Пер. с англ. / Предисл. В. П. Козырева; Под ред. Г.П.Гаврилова. Изд. 4-е. — М.: Книжный дом «ЛИБРОКОМ», 2009. — 60 с.
- Дж. Клейнберг, Е. Тардос. Алгоритмы: разработка и применение. Классика Computers Science. 2016. — 383 c.