Liczba minut wykresu bez użycia algorytmu Kargera

Wiemy, że algorytm wycinania Kargera można wykorzystać do udowodnienia (w niekonstruktywny sposób), że maksymalna liczba możliwych skrótów może mieć wykres $n \choose 2$ .

Zastanawiałem się, czy moglibyśmy w jakiś sposób udowodnić tę tożsamość, podając bijectywny (raczej iniekcyjny) dowód z zestawu skrótów do innego zestawu liczności $n \choose 2$ . Bez konkretnych powodów, to tylko ciekawość. Próbowałem to zrobić sam, ale jak dotąd nie odniosłem żadnego sukcesu. Nie chciałbym, aby ktokolwiek marnował czas na to, więc jeśli pytanie wydaje się bezcelowe, prosiłbym moderatorów o podjęcie odpowiednich działań.

Najlepszy -Akash

$\binom{n}{2}$ związany myślę został sprawdzony przez Dinitz, Karzanov i Lomonosov 1976, w „strukturę A dla układu wszelkich minimalnych kawałków wykresu”. Być może możesz znaleźć to, czego szukasz w tym artykule, ale nie jestem pewien, czy jest online.

Nieformalnie można argumentować, że aby uzyskać maksymalną liczbę minimalnych cięć, wszystkie węzły na wykresie muszą mieć ten sam stopień.

Niech cięcie podzieli wykres na dwa zestawy węzłów i tak, że . Niech liczba minimalnych cięć na wykresie będzie oznaczona jako .$G$$C$$\bar C$$C \cap \bar C=\emptyset$$mc(G)$

Rozważ połączony wykres z wierzchołkami, w których każdy wierzchołek ma stopień drugi. To musi być wykres cyklu, a minimalne cięcie to dwie krawędzie. Oczywiste jest, że cięcie dowolnych dwóch krawędzi spowoduje cięcie i że takie cięcie jest minimalnym cięciem. Ponieważ istnieje odrębne pary krawędzi, istnieje minimalne nacięcia.$n$$n(n-1)/2$$n(n-1)/2$

Utwórz nowy wykres, usuwając krawędź z wykresu cyklu. Minimalne cięcie nowego wykresu to jedna krawędź i wystarczy przecięcie dowolnej krawędzi: istnieje takich cięć, które można wykonać.$n-1$

Utwórz nowy wykres, dodając krawędź do wykresu cyklu. Teraz dwa węzły mają stopień trzeci, a węzły mają stopień drugi. Stopień trzy węzły muszą obie należą do lub obie należą do . Należy zauważyć, że w przypadku wykres cyklu nie były ograniczone do węzłów występują razem w i . Oznacza to, że dodanie krawędzi dodaje ograniczenie, które zmniejsza liczbę minimalnych cięć.$n-2$$C$$\bar C$$C$$\bar C$

Promowanie większej liczby węzłów do stopnia trzeciego dodaje dodatkowe ograniczenia do momentu, w którym jest tylko jedno minimalne cięcie stopnia drugiego.

Powyższe pokazuje, że wykres cyklu jest (przynajmniej) lokalnym maksimum .$mc$

Rozważ zestaw wykresów, w którym każdy węzeł ma stopień trzeci. Usunięcie krawędzi daje wykres z jednym cięciem minimalnym wynoszącym dwa. Dodanie krawędzi, jak powyżej, tworzy dwa węzły, które najbardziej pojawiają się po tej samej stronie cięcia.

Sugeruje to, że wykresy, w których każdy węzeł ma stopień są lokalnymi maksimami . Zauważenie, że pełny wykres ma cięć o rozmiarze sugeruje, że jest to funkcja malejąca.$k$$mc$$mc=n$$n-1$

Nie zastanawiałem się nad tym, czy można sformalizować powyższe, ale stanowi to możliwe podejście.

Ponadto myślę, że artykuł Bixby, o którym wspomina Jelani Nelson w komentarzu do swojej odpowiedzi, zatytułowany jest „Minimalna liczba krawędzi i wierzchołków na wykresie z łącznością krawędzi n i M n-obligacjami” ( link )