/math/ - Сап, математач! Кто-нибудь шарит в графах? Нужно понять, как доказать, что минимальное рёберное покр

Сап, математач! Кто-нибудь шарит в графах? Нужно понять, как доказать, что минимальное рёберное покр Аноним 02/06/23 Птн 12:14:25 № 102849 1

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

Аноним 03/06/23 Суб 21:38:14 № 102875 2

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

Аноним 03/06/23 Суб 21:38:51 № 102876 3

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