М.Двач / Математика

105 Кб, 567x654
Сап, математач! Кто-нибудь шарит в графах? Нужно понять, как доказать, что минимальное рёберное покр 2 июня 2023, 12:14 102849 В конец треда | Веб

Сап, математач! Кто-нибудь шарит в графах? Нужно понять, как доказать, что минимальное рёберное покрытие имеет мощность не более чем ND/(D+1), где N - число вершин, а D - максимальная степень вершины. Предполагается, что в графе нет изолированных вершин.
Пока в голову приходит только то, что можно взять вершину, имеющую максимальную степень, и в покрытие включить все инцидентные ей рёбра, тем самым покрыв D+1 вершину D рёбрами, затем исключить все покрытые вершины из графа и продолжить этот процесс, пока граф не опустеет. Но проблема в том, что в процессе такого удаления частей графа могут появиться изолированные вершины, которые в результате останутся непокрытыми.

50 Кб, 712x578
2 3 июня 2023, 21:38 2 102875

может наоборот, выбирать вершину с минимальной степенью и ее удалять? Тогда вроде все норм должно быть, и отношение ND/(D+1) должно сохраняться, и изолированных вершин не должно появляться

50 Кб, 712x578
3 3 июня 2023, 21:38 3 102876

Обновить тред
« /math/В начало тредаВеб-версияНастройки/a//b//mu//s//vg/Все доски

Скачать тред только с превьюс превью и прикрепленными файлами

Второй вариант может долго скачиваться. Файлы будут только в живых или недавно утонувших тредах.Подробнее

Пользуетесь скринридером — пишите, что можно улучшить.
Host-Food.ru — надёжный хостинг от 12 руб/мес | Free DNS
Зеркала М.Двача: m2ch.hk, m2ch.lib, m2chfapiswfw2wcakptqp4o6ltgchvjuxfab7urxlduraomtlnhw5xad.onion