Минимальное количество ребер в графе

@hzeds · Регистрация: 04.03.2019

Студворк — интернет-сервис помощи студентам

Дано n вершин и m ребер в неориентированном графе. Далее идет по два числа - вершины ребер. Вывести целое число k - минимальное количество ребер, которые нужно добавить, чтобы выполнялось условие: когда для любых трех различных вершин u, v, k если существуют ребра (u, v) и (v, k), то существует и ребро (v, k).
Input
3 2
1 2
2 3
Output
1

@ReDoX · 04.03.2019, 21:50

Сообщение от hzeds

если существуют ребра (u, v) и (v, k), то существует и ребро (v, k).

Если существует ребро (v, k), то существует ребро (v, k)

Может быть: если существует ребра (u, v) и (v, k), то существует и ребро (u, k)?

@hzeds · 04.03.2019, 23:24 **[ТС]**

Сообщение от ReDoX

Может быть: если существует ребра (u, v) и (v, k), то существует и ребро (u, k)?

Вы правы, опечатка.

Байт · 05.03.2019, 12:08

Называется - "транзитивное замыкание"
Или это только для ориентированных?
А тут будет, скорее всего, "эквивалентное замыкание". Т.е. разбитие на компоненты связности с достраиванием каждой компоненты до полного графа.

IGPIGP · 05.03.2019, 14:04

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

Байт · 05.03.2019, 14:44

Не заметил, что нужно только вывести количество. Тогда все проще. Находим компоненты связности. Считаем, сколько должно быть ребер для ее полноты. Если в компоненте m вершин, то это число = m(m-1)/2
Суммируем по всем компонентам - вот столько ребер должно быть

Сообщение от IGPIGP

на мой взгляд нужно добавлять рёбра к тем вершинам которые имеют минимальное количество рёбер

Это, конечно, не так, а значительно проще.

Добавлено через 26 минут
Вопрос, как эти компоненты найти.
Я бы делал так. Берем столбец матрицы смежности. Находим единичку в строке x. столбец x булевой операцией |= соединяем с просматриваемым. Найденную единичку обнуляем. Столбец x удаляем (помечаем удаленным) И так пока единички есть. Одна компонента готова. По дороге можно посчитать количество вершин, попавших в нее и ребер (если нужно). Переходим к следующему не удаленному столбцу.

@hzeds · 07.03.2019, 21:14 **[ТС]**

Сообщение от Байт

Не заметил, что нужно только вывести количество. Тогда все проще. Находим компоненты связности. Считаем, сколько должно быть ребер для ее полноты. Если в компоненте m вершин, то это число = m(m-1)/2

Так?

C++
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
#include <iostream>
#include <vector>
#include <algorithm>
#define MAXN 100001
 
using namespace std;
int n, m, s;
vector<int> g[MAXN];
bool used[MAXN];
vector<int> comp;
void dfs (int v)
{
    used[v] = true;
    comp.push_back (v);
    for (size_t i=0; i<g[v].size(); ++i)
    {
        int to = g[v][i];
        if (! used[to]) dfs (to);
    }
}
void find_comps()
{
    for (int i=0; i<n; ++i) used[i] = false;
    for (int i=0; i<n; ++i)
        if (! used[i])
        {
            comp.clear();
            dfs (i);
            sort(comp.begin(),comp.end());
            cout << "Component: ";
            for (size_t j=0; j<comp.size(); ++j) cout << comp[j]+1 <<' ';
                cout << endl;
        }
}
int main()
{
    cin >> n >> m;
    for (int i=0; i<m; ++i)
    {
        int u, v;
        cin >> u >> v;
        g[u-1].push_back(v-1);
        g[v-1].push_back(u-1);
    }
    find_comps();
    cout << "Full Ribs = " << (n/2)*(n-1);
    return 0;
}

@hzeds · 08.03.2019, 22:19 **[ТС]**

Добавлено через 3 часа 5 минут
Байт, Спасибо, разобрался. ))

Байт · 08.03.2019, 23:36

Сообщение от hzeds

Спасибо, разобрался. ))

Молодец!

Не жди милостей у умников! Стань им сам! Стань умнее, чем они!

Удачи!

Добавлено через 25 минут
hzeds, Почему-то вот что захотелось сказать. Графы - штука серьезная. Имеющая кучу приложений в "народном хозяйстве" Ибо очень много серьезных и нужных задач формулируются именно в терминах теории графов. И люди по всему миру пытаются их решить как можно лучше. Мы с тобой решали одну из задач - найти компоненты связности. Я предложил в посте 6 некий работающий алгоритм - просто первое, что в голову пришло. Но я уверен, что в мире есть и более эффективные и ловкие алгоритмы. Некоторые из них даже носят имена их придумщиков. Все это нонче легко найти в интернете. Это я к тому, что если твоя задача не является для тебя последней в этой очень интересной области.
А то, что ты сумел переложить в рабочий код эти несколько строчек, делает тебе честь.

Новые блоги и статьи Все статьи Все блоги /
SDL3 для Desktop (MinGW): Создаём пустое окно с нуля для 2D-графики на SDL3, Си и C++ 8Observer8 10.03.2026 Содержание блога Финальные проекты на Си и на C++: hello-sdl3-c. zip hello-sdl3-cpp. zip Результат:	Установка CMake и MinGW 13.1 для сборки С и C++ приложений из консоли и из Qt Creator в EXE 8Observer8 10.03.2026 Содержание блога MinGW - это коллекция инструментов для сборки приложений в EXE. CMake - это система сборки приложений. Здесь описаны базовые шаги для старта программирования с помощью CMake и. . .	Как дизайн сайта влияет на конверсию: 7 решений, которые реально повышают заявки Neotwalker 08.03.2026 Многие до сих пор воспринимают дизайн сайта как “красивую оболочку”. На практике всё иначе: дизайн напрямую влияет на то, оставит человек заявку или уйдёт через несколько секунд. Даже если у вас. . .	Модульная разработка через nuget packages DevAlt 07.03.2026 Сложившийся в . Net-среде способ разработки чаще всего предполагает монорепозиторий в котором находятся все исходники. При создании нового решения, мы просто добавляем нужные проекты и имеем. . .
Модульный подход на примере F# DevAlt 06.03.2026 В блоге дяди Боба наткнулся на такое определение: В этой книге («Подход, основанный на вариантах использования») Ивар утверждает, что архитектура программного обеспечения — это структуры,. . .	Управление камерой с помощью скрипта OrbitControls.js на Three.js: Вращение, зум и панорамирование 8Observer8 05.03.2026 Содержание блога Финальная демка в браузере работает на Desktop и мобильных браузерах. Итоговый код: orbit-controls-threejs-js. zip. Сканируйте QR-код на мобильном. Вращайте камеру одним пальцем,. . .	SDL3 для Web (WebAssembly): Синхронизация спрайтов SDL3 и тел Box2D 8Observer8 04.03.2026 Содержание блога Финальная демка в браузере. Итоговый код: finish-sync-physics-sprites-sdl3-c. zip На первой гифке отладочные линии отключены, а на второй включены:. . .	SDL3 для Web (WebAssembly): Идентификация объектов на Box2D v3 - использование userData и событий коллизий 8Observer8 02.03.2026 Содержание блога Финальная демка в браузере. Итоговый код: finish-collision-events-sdl3-c. zip Сканируйте QR-код на мобильном и вы увидите, что появится джойстик для управления главным героем. . . .

@hzeds 1 / 1 / 0 Регистрация: 04.03.2019 Сообщений: 27

	Минимальное количество ребер в графе 04.03.2019, 21:11. Показов 8521. Ответов 8 Метки нет (Все метки) Дано n вершин и m ребер в неориентированном графе. Далее идет по два числа - вершины ребер. Вывести целое число k - минимальное количество ребер, которые нужно добавить, чтобы выполнялось условие: когда для любых трех различных вершин u, v, k если существуют ребра (u, v) и (v, k), то существует и ребро (v, k). Input 3 2 1 2 2 3 Output 1 0

Байт Диссидент 27714 / 17332 / 3810 Регистрация: 24.12.2010 Сообщений: 38,978
	05.03.2019, 12:08
	Называется - "транзитивное замыкание" Или это только для ориентированных? А тут будет, скорее всего, "эквивалентное замыкание". Т.е. разбитие на компоненты связности с достраиванием каждой компоненты до полного графа. 1

IGPIGP Комп_Оратор) $Эксперт по математике/физике$ 9007 / 4708 / 630 Регистрация: 04.12.2011 Сообщений: 14,003 Записей в блоге: 16
	05.03.2019, 14:04
	hzeds, на мой взгляд нужно добавлять рёбра к тем вершинам которые имеют минимальное количество рёбер. Тогда число замыканий (до треугольников) будет минимально. 1

@hzeds 1 / 1 / 0 Регистрация: 04.03.2019 Сообщений: 27
	08.03.2019, 22:19 [ТС]
	Добавлено через 3 часа 5 минут Байт, Спасибо, разобрался. )) 1

Минимальное количество ребер в графе

Решение