Numer skrzyżowania (teoria grafów)

W matematycznej dziedzinie teorii grafów numer przecięcia wykresu jest najmniejszą liczbą elementów w reprezentacji jako sol $E)}$ $Displaystyle G = ($ wykres przecięcia zbiorów skończonych . W takiej reprezentacji każdy wierzchołek jest reprezentowany jako zbiór, a dwa wierzchołki są połączone krawędzią, ilekroć ich zbiory mają wspólny element. Równoważnie numer przecięcia to najmniejsza liczba klik potrzebnych do pokrycia wszystkich krawędzi ${\ displaystyle G}$ .

Zbiór klik pokrywających wszystkie krawędzie grafu nazywany jest pokryciem kliki lub pokryciem kliki krawędziowej , a nawet po prostu pokryciem kliki , chociaż ostatni termin jest niejednoznaczny: pokrycie kliki może być również zbiorem klik obejmujących wszystkie wierzchołki wykresu. Czasami „pokrycie” jest używane zamiast „pokrycia”. Minimalna liczba tych klik nie tylko nazywana jest numerem przecięcia, ale także nazywana jest zawartością R , numerem pokrycia kliki brzegowej lub numerem pokrycia kliki . Problem obliczania liczby przecięć został nazwany problemem liczby przecięć , problemem podstawy grafu przecięć , pokryciem przez kliki , problemem pokrycia kliki krawędzi oraz problemem konfliktu słów kluczowych .

Każdy wykres z $}$ i $min$ ma co najwyżej liczbę przecięć ${\ Displaystyle \ min (m, n ^ {2}/4$ . Numer skrzyżowania jest NP-trudny do obliczenia lub przybliżenia, ale możliwy do zastosowania ze stałymi parametrami .

Definicje

Wykresy przecięć

Niech $będzie$ dowolną rodziną zestawów , pozwalającą na powtarzanie w ${\ displaystyle {\ mathcal {F}}} .$ Wtedy $}$ przecięcia z jest nieskierowanym wykresem , który ma wierzchołek dla każdego zestawu w $}$ i krawędź między każdymi dwoma zestawami, które mają niepuste przecięcie. Każdy graf można przedstawić w ten sposób jako graf przecięcia. Numer przecięcia wykresu to najmniejsza liczba $,$ dla której suma zbiorów w ma $}$ ${\ displaystyle k}$ elementów. Problem znalezienia reprezentacji przecięcia grafu o danej liczbie elementów jest znany jako problem podstawy grafu przecięcia .

Clique okładki krawędzi

Wykres ze skrzyżowaniem numer cztery. Cztery zacienione regiony wskazują kliki, które pokrywają wszystkie krawędzie wykresu.

Alternatywna definicja numeru przecięcia wykresu $jest taka$ $G}$ że jest to najmniejsza liczba klik w ( pełne $podwykresy$ , które razem pokrywają wszystkie krawędzie sol { \ z ${\ Displaystyle G}$ . Zbiór klik o tej właściwości jest znany jako pokrycie krawędzi kliki lub pokrycie kliki krawędzi iz tego powodu numer przecięcia jest czasami nazywany numer okładki Edge Clique .

Równorzędność

Równość numeru przecięcia i numeru pokrycia kliki krawędziowej jest łatwa do udowodnienia. W jednym kierunku załóżmy, $że$ $.$ wykresem $suma$ rodziny zbiorów $,$ ma Następnie dla dowolnego elementu podzbiór wierzchołków odpowiadający zestawom zawierającym $\ in U}$ $\ Displaystyle x$ ${\ displaystyle x}$ tworzy klikę: dowolne dwa wierzchołki w tym podzbiorze sąsiadują ze sobą, ponieważ ich zbiory mają niepuste przecięcie zawierające ${\ displaystyle x}$ . Co więcej, każda krawędź w $klik$ : jeśli krawędź pochodzi z niepustego przecięcia zbiorów zawierających element ${\ displaystyle y}$ to ta krawędź jest zawarta w kliku dla sol y ${\ displaystyle y}$ . krawędzie $k$ być objęte $kliki$ , po jednej na element ${\ displaystyle U}$ .

Z drugiej strony, jeśli wykres $z$ być objęty $klikami$ , to każdy wierzchołek $może$ przez podzbiór sol { $displaystyle G}$ kliki, te, które zawierają wierzchołek ${\ displaystyle v}$ . $Dwa$ z tych podzbiorów, dla dwóch wierzchołków v $\ displaystyle v}$ $, gdy w przecięciu$ się klika, która zawiera je obie, wtedy i tylko wtedy, gdy istnieje krawędź w jednej z pokrywających klik.

Aplikacje

Reprezentacja wykresu jako abstrakcyjnego wykresu przecięcia zbiorów może być wykorzystana do skonstruowania bardziej konkretnych geometrycznych reprezentacji przecięcia tego samego wykresu. W szczególności, jeśli wykres ma numer przecięcia $można$ go przedstawić jako wykres przecięcia hipersześcianów jednostek wymiarowych (co oznacza, że jego pudełkowatość wynosi co najwyżej $k {\ displaystyle k$ $\ displaystyle k$ } lub jako wykres $przecięcia$ hipersfer jednostkowych (jego sferyczność jest co najwyżej ${\ displaystyle k}$ ).

Pokrycie kliki może być użyte jako rodzaj schematu oznaczania przylegania grafu, w którym każdy wierzchołek oznacza się wartością binarną z bitem dla każdej kliki, zerem, jeśli nie należy do kliki, i jednym, jeśli należy. Wtedy dwa wierzchołki sąsiadują ze sobą wtedy i tylko wtedy, gdy bitowe i ich etykiet jest niezerowe. Długość etykiet to numer przecięcia wykresu. Ta metoda została wykorzystana we wczesnym zastosowaniu numerów skrzyżowań do etykietowania zestawu słów kluczowych, aby można było szybko wykryć sprzeczne słowa kluczowe, przez E. Kellermana z IBM. Z tego powodu inną nazwą problemu obliczania numerów skrzyżowań jest tzw problem z konfliktem słów kluczowych . Podobnie w geometrii obliczeniowej reprezentacje oparte na liczbie przecięć były uważane za zwartą reprezentację wykresów widoczności , ale istnieją geometryczne dane wejściowe, dla których ta reprezentacja wymaga niemal kwadratowej liczby klik.

Inna klasa aplikacji pochodzi z problemów z planowaniem , w których wielu użytkowników współdzielonego zasobu powinno być przypisanych do przedziałów czasowych w taki sposób, że niekompatybilne żądania nigdy nie są planowane dla tego samego przedziału czasowego, ale wszystkie pary zgodnych żądań są przydzielane co najmniej raz gniazdo razem. Numer przecięcia wykresu zgodności określa minimalną liczbę przedziałów czasowych wymaganych dla takiego harmonogramu. W projektowaniu kompilatorów dla bardzo długich instrukcji słowo komputery, małe pokrycie kliki wykresu niekompatybilnych operacji może być użyte do przedstawienia ich niezgodności za pomocą niewielkiej liczby sztucznych zasobów, umożliwiając wykorzystanie technik planowania opartych na zasobach do przypisania operacji do przedziałów instrukcji.

Shephard i Vetta zauważają, że liczba przecięć dowolnej sieci jest równa minimalnej liczbie ograniczeń potrzebnych w sformułowaniu problemu obliczania maksymalnych niezależnych zbiorów w programowaniu całkowitym , w którym jeden ma zmienną 0-1 na wierzchołek i ograniczenie, które w każdej kliki kliki obejmuje zmienne, które sumują się co najwyżej do jednego. Twierdzą, że w przypadku wykresów przecięć ścieżek w niektórych światłowodowych sieciach komunikacyjnych te liczby przecięć są małe, co wyjaśnia względną łatwość rozwiązywania pewnych problemów optymalizacyjnych przy alokacji przepustowości w sieciach.

W statystyce i wizualizacji danych krawędziowe pokrycia kliki wykresu reprezentujące statystycznie nierozróżnialne pary zmiennych są używane do tworzenia zwartych wyświetlaczy liter , które pomagają w wizualizacji wielu porównań parami, poprzez przypisanie litery lub innego znacznika wizualnego do każdej kliki i wykorzystanie ich do zapewnienia graficzne przedstawienie, które zmienne są nierozróżnialne.

W analizie sieci pokarmowych opisujących relacje drapieżnik-ofiara między gatunkami zwierząt graf konkurencji lub graf nakładania się nisz jest grafem nieukierunkowanym, w którym wierzchołki reprezentują gatunki, a krawędzie reprezentują pary gatunków, które rywalizują o tę samą zdobycz. Można je wyprowadzić z skierowanego acyklicznego wykresu reprezentującego relacje drapieżnik-ofiara $,$ rysując krawędź , ilekroć istnieje gatunek ofiary. ${\ displaystyle w}$ $}$ że wykres relacji drapieżnik-ofiara ma krawędzie $do w$ \ . Każdy graf konkurencji musi mieć co najmniej jeden izolowany wierzchołek i numer konkurencji dowolnego grafu reprezentuje najmniejszą liczbę izolowanych wierzchołków, które można dodać, aby utworzyć z niego graf współzawodnictwa. Z biologicznego punktu widzenia, jeśli obserwuje się część wykresu współzawodnictwa, wówczas liczba współzawodnictwa reprezentuje najmniejszą możliwą liczbę nieobserwowanych gatunków ofiar potrzebną do wyjaśnienia tego. Liczba współzawodnictwa jest co najwyżej równa liczbie przecięcia: dowolny graf nieskierowany można przekształcić w graf współzawodnictwa, dodając gatunek zdobyczy dla każdej kliki w pokryciu kliki krawędziowej. Jednak ta zależność nie jest dokładna, ponieważ gatunek drapieżnika może być również ofiarą innego gatunku. Na wykresie z ${\ displaystyle n}$ $n$ najwyżej z nich może być ofiarą więcej niż jednego innego gatunku, więc liczba konkurencji to co najmniej liczba przecięcia 2 $n-2}$ .

Osłony kliki brzegowej zostały również wykorzystane do wywnioskowania istnienia kompleksów białkowych , systemów wzajemnie oddziałujących białek, z sieci interakcji białko-białko opisujących tylko interakcje parami między białkami. Mówiąc bardziej ogólnie, Guillaume i Latapy argumentowali, że w przypadku złożonych sieci wszystkich typów zastąpienie sieci grafem dwudzielnym łączącym jej wierzchołki z klikami w pokryciu kliki podkreśla strukturę sieci.

Górne granice

$przecięć$ wykres z $liczbę$ ma co najwyżej . Każda krawędź sama w sobie jest dwuwierzchołkową kliką. $Tych$ jest i razem pokrywają wszystkie krawędzie. Prawdą jest również, że każdy wykres z $wierzchołkami$ ma co najwyżej liczbę przecięć ${\ displaystyle \ lfloor n ^ {2}/4 \ rfloor$ . Silniej krawędzie każdego ${\ displaystyle n}$ Wykres -wierzchołków może być pokryty co najwyżej $.$ wszystkie są albo pojedynczymi krawędziami Algorytm znajdowania tego pokrycia jest prosty: usuń dwa sąsiednie wierzchołki i pokryj indukcyjnie pozostały wykres. Przywracając dwa usunięte wierzchołki, zakryj krawędzie ich wspólnych sąsiadów trójkątami, pozostawiając krawędzie niewspólnym sąsiadom jako kliki dwóch wierzchołków. Powłoka indukcyjna ma co najwyżej ${\ Displaystyle \ lfloor (n-2) ^ {2}/4 \ rfloor}$ $kliki$ , a dwa usunięte wierzchołki wnoszą co najwyżej zmaksymalizowane, gdy wszystkie inne wierzchołki są niewspółdzielonymi sąsiadami krawędź między dwoma wierzchołkami musi być używana jako klika. Dodanie tych $_$ To uogólnia twierdzenie Mantela , że wykres bez trójkątów ma co najwyżej ${\ displaystyle \ lfloor n ^ {2}/4 \ rfloor}$ krawędzie, ponieważ na wykresie bez trójkątów jedyne optymalne pokrycie krawędzi kliki ma jedną klikę na krawędź, a zatem liczba przecięć jest równa liczbie krawędzi.

Jeszcze ściślejsze ograniczenie jest możliwe, gdy liczba krawędzi jest ściśle większa niż ${\ displaystyle {\ tfrac {n ^ {2}} {4}}}$ . Niech ${\ displaystyle p}$ będzie liczbą par wierzchołków, które nie są połączone krawędzią w danym grafie $($ niech będzie unikalną liczbą całkowitą, dla której $\ displaystyle G}$ ${\ Displaystyle (t-1) t \ równoważnik p <t (t + 1)}$ . Wtedy numer przecięcia $displaystyle$ co najwyżej $p + t}$ . Wykresy, które są wykresu , mają małe liczby przecięć: liczba przecięć dowolnego $wierzchołków$ wynosi najwyżej $)$ ${\ Displaystyle 2e ^ {2} (d + 1) ^ {2} \ ln n}$ , gdzie ${\ Displaystyle e}$ jest podstawą logarytmu naturalnego , a ${\ Displaystyle d}$ jest maksymalnym stopniem dopełnienia wykres sol $\ displaystyle G}$ .

$wyników$ dotyczących struktury grafów bez pazurów wynika że gdy połączony $wierzchołków$ ma co najmniej trzy niezależne wierzchołki, ma co najwyżej liczbę przecięć . Pozostaje nierozwiązanym problemem, czy dotyczy to wszystkich grafów bez pazurów bez wymogu posiadania przez nie dużych niezależnych zbiorów. Ważną podklasą wykresów bez pazurów są wykresy liniowe , wykresy przedstawiające krawędzie i dotykające pary krawędzi jakiegoś innego wykresu ${\ displaystyle G}$ . Optymalne pokrycie kliki wykresu liniowego $\$ utworzyć z jedną kliką dla każdego trójkąta w, $displaystyle G}$ jedną klikę dla sol { każdy wierzchołek, który ma stopień co najmniej dwa i nie jest wierzchołkiem stopnia drugiego jednego z tych trójkątów. Liczba przecięć to liczba klik tych dwóch typów.

W modelu grafów losowych Erdősa – Rényi – Gilberta , w którym wszystkie wykresy na $wierzchołkach$ są równie prawdopodobne (lub równoważnie, każda krawędź jest obecna lub nieobecna, niezależnie od innych krawędzi, z prawdopodobieństwem ${\ displaystyle {\ tfrac {1}{2}}}$ ) liczba przecięć losowego wykresu wierzchołków jest z dużym prawdopodobieństwem ${\ displaystyle n}$

{\ Displaystyle \ Theta \ lewo ({\ Frac {n ^ {2}} {\ log ^ {2} n}} \ prawej),}

mniejszy o współczynnik

{\ displaystyle \ log ^ {2} n}

niż liczba krawędzi. Na tych grafach maksymalne kliki mają (z dużym prawdopodobieństwem) tylko logarytmiczną liczbę wierzchołków, co sugeruje, że tak wiele z nich jest potrzebnych do pokrycia wszystkich krawędzi. Podstępną częścią ograniczenia jest udowodnienie, że możliwe jest znalezienie wystarczającej liczby klik o wielkości logarytmicznej, aby pokryć wiele krawędzi, pozwalając na pokrycie pozostałych pozostałych krawędzi przez kliki o dwóch wierzchołkach.

Wiele wczesnych badań nad liczbami przecięć obejmowało obliczanie tych liczb na różnych określonych wykresach, takich jak wykresy utworzone przez usunięcie pełnego podgrafu lub idealne dopasowanie z większego pełnego wykresu.

Złożoność obliczeniowa

$,$ czy dany wykres $NP$ co najwyżej numer przecięcia danej liczby, - zupełne . Dlatego obliczenie numeru przecięcia danego wykresu jest również NP-trudne. Z kolei twardość numeru przecięcia została wykorzystana do udowodnienia, że rozpoznawanie kwadratów grafów podzielonych jest NP-zupełne .

Problem obliczania numeru skrzyżowania jest jednak możliwy do rozwiązania ze stałymi parametrami : to znaczy można $go$ rozwiązać w czasie ograniczonym wielomianem przez większą, ale obliczalną funkcję numeru skrzyżowania ${\ displaystyle k}$ . Można to wykazać, obserwując, że istnieją co najwyżej różne zamknięte sąsiedztwa ${\ displaystyle 2 ^ {k}}$ na grafie - dwa wierzchołki należące do tego samego zestawu klik mają to samo sąsiedztwo - oraz że graf utworzony przez wybranie jednego wierzchołka na zamknięte sąsiedztwo ma taki sam numer przecięcia jak graf oryginalny. $krawędziami$ $w$ wejściowe można zredukować do z co najwyżej i Zastosowanie procedury wyszukiwania dynamicznego programowania w czasie wykładniczym na podzbiorach krawędzi tego jądra daje czas ${\ Displaystyle 2 ^ {O (4 ^ {k})} + n ^ {O (1)}}$ , podwójnie wykładniczy w ${\ Displaystyle k}$ . Podwójnej wykładniczej zależności od $nie$ można zredukować do pojedynczej wykładniczej przez jądrowanie rozmiaru wielomianu, chyba że wielomianów się załamie i jeśli hipoteza czasu wykładniczego jest prawdą, to podwójna wykładnicza zależność jest konieczna niezależnie od tego, czy używana jest kernelizacja. Na grafach o ograniczonej szerokości drzewa dynamiczne programowanie na dekompozycji drzewiastej grafu może znaleźć numer przecięcia w czasie liniowym, ale prostsze algorytmy oparte na skończonych zbiorach reguł redukcji nie działają.

Problemu nie można przybliżyć w czasie wielomianowym ze $przybliżenia$ lepszym niż , dla pewnej stałej $a$ znany współczynnik przybliżenia jest lepszy niż trywialny ${\ Displaystyle O (n ^ {2})}$ tylko przez czynnik polilogarytmiczny. Badacze zajmujący się tą dziedziną badali również wydajność obliczeniową heurystyk, bez gwarancji co do jakości tworzonych przez nie rozwiązań, oraz ich zachowania w rzeczywistych sieciach.

Dla pewnych specjalnych klas grafów znane są bardziej wydajne algorytmy. Liczba przecięć wykresu interwałowego jest zawsze równa liczbie jego maksymalnych klik , które można obliczyć w czasie wielomianowym. Mówiąc bardziej ogólnie, w grafach akordowych liczbę przecięć można obliczyć za pomocą algorytmu, który uwzględnia wierzchołki w kolejności eliminacji grafu (uporządkowanie, w którym każdy wierzchołek i jego późniejsi sąsiedzi tworzą klikę) i że dla każdego wierzchołka ${ \ displaystyle v}$ tworzy klikę dla ${\ displaystyle v}$ i jego późniejszych sąsiadów, ilekroć co najmniej jedna z krawędzi incydentnych z $jest$ pokryta żadną wcześniejszą kliką. Możliwe jest również znalezienie numeru przecięcia w czasie liniowym na wykresach łukowych . Jednakże, chociaż te grafy mają tylko wielomianową liczbę klik do wyboru na okładkę, samo posiadanie kilku klik nie wystarczy, aby rozwiązać problem: istnieją rodziny grafów z wielomianowo wieloma klikami, dla których liczba przecięć pozostaje NP-trudna . Liczbę przecięć można również znaleźć w czasie wielomianowym dla wykresów, których maksymalny stopień wynosi pięć, ale jest to NP-trudne dla wykresów o maksymalnym stopniu sześciu. Na grafach planarnych dokładne obliczenie liczby przecięć pozostaje NP-trudne, ale ma schemat aproksymacji w czasie wielomianowym oparty na technice Bakera .

Zobacz też

Wymiar dwudzielny , najmniejsza liczba bicliques potrzebna do pokrycia wszystkich krawędzi grafu
Pokrycie kliki , problem NP-trudny polegający na znalezieniu niewielkiej liczby klik obejmujących wszystkie wierzchołki grafu

Linki zewnętrzne

Weisstein, Eric W. , „Numer skrzyżowania” , MathWorld