Pseudolas - Pseudoforest

1-las (maksymalny pseudolas), utworzony przez trzy 1-drzewa

W teorii wykres , A pseudoforest jest nieukierunkowane wykres , w którym każdy połączony komponent zawiera co najwyżej jeden cykl . Oznacza to, że jest to układ wierzchołków i krawędzi łączących pary wierzchołków w taki sposób, że żadne dwa cykle następujących po sobie krawędzi nie mają wspólnego wierzchołka, ani żadne dwa cykle nie mogą być połączone ze sobą ścieżką kolejnych krawędzi. Pseudotree jest podłączone pseudoforest.

Nazwy uzasadniane są przez analogię do częściej badanych drzew i lasów . (Drzewo jest połączonym grafem bez cykli; las to rozłączny związek drzew). Gabow i Tarjan przypisują badanie pseudolasów książce Dantzig z 1963 r. o programowaniu liniowym , w której pseudolasy powstają w celu rozwiązania pewnych problemów z przepływem sieci . Pseudolasy tworzą również modele funkcji oparte na teorii grafów i występują w kilku problemach algorytmicznych . Pseudolasy są grafami rzadkimi – ich liczba krawędzi jest liniowo ograniczona pod względem liczby wierzchołków (w rzeczywistości mają co najwyżej tyle krawędzi, ile mają wierzchołków) – a ich struktura matroidalna pozwala na rozkład kilku innych rodzin grafów rzadkich jako związki lasów i pseudolasów. Nazwa „pseudolas” pochodzi od Picarda i Queyranne'a (1982) .

Definicje i struktura

Definiujemy graf nieskierowany jako zestaw wierzchołków i krawędzi, tak że każda krawędź ma dwa wierzchołki (które mogą się pokrywać) jako punkty końcowe. Oznacza to, że dopuszczamy wiele krawędzi (krawędzie z tą samą parą punktów końcowych) i pętle (krawędzie, których dwa punkty końcowe są tym samym wierzchołkiem). Subgraph wykresu jest wykresem formowana dowolnymi podzbiorów swoich wierzchołkach i krawędziach, tak, że każda krawędź w podgrupie krawędź ma oba punkty końcowe w podgrupie wierzchołków. Podłączone urządzenie o nieukierunkowane wykresu jest subgraph składający wierzchołkach i krawędziach, które mogą być osiągnięte przez następujące krawędzi z jednym danego wierzchołka wyjściowego. Wykres jest połączony, jeśli każdy wierzchołek lub krawędź jest osiągalny z każdego innego wierzchołka lub krawędzi. Cykl w nieukierunkowane wykresu jest podłączone subgraph w którym każdy wierzchołek pada na dokładnie dwie krawędzie czy pętla.

21 jednocyklicznych grafów z co najwyżej sześcioma wierzchołkami

Pseudolas to graf nieskierowany, w którym każdy połączony składnik zawiera co najwyżej jeden cykl. Równoważnie jest to graf nieskierowany, w którym każdy połączony komponent ma nie więcej krawędzi niż wierzchołków. Komponenty, które nie mają cykli, są tylko drzewami , podczas gdy komponenty, które mają w sobie jeden cykl, nazywane są 1-drzewami lub grafami jednocyklicznymi . Oznacza to, że 1-drzewo to połączony wykres zawierający dokładnie jeden cykl. Pseudolas z pojedynczym połączonym składnikiem (zwykle nazywany pseudodrzewem , chociaż niektórzy autorzy definiują pseudodrzewo jako jedno drzewo) to albo drzewo, albo jedno drzewo; ogólnie rzecz biorąc, pseudolas może mieć wiele połączonych komponentów, o ile wszystkie z nich są drzewami lub 1-drzewami.

Jeśli usunie się z jednego drzewa jedną z krawędzi w jego cyklu, wynikiem jest drzewo. Odwracając ten proces, jeśli ktoś powiększa drzewo, łącząc dowolne dwa z jego wierzchołków nową krawędzią, wynikiem jest 1-drzewo; ścieżka w drzewie łącząca dwa punkty końcowe dodanej krawędzi, wraz z samą dodaną krawędzią, tworzą unikalny cykl 1-drzewa. Jeśli ktoś powiększa jedno drzewo, dodając krawędź, która łączy jeden z jego wierzchołków z nowo dodanym wierzchołkiem, wynikiem jest znowu jedno drzewo z jeszcze jednym wierzchołkiem; alternatywną metodą konstruowania 1-drzew jest rozpoczęcie od jednego cyklu, a następnie powtórzenie tej operacji augmentacji dowolną liczbę razy. Krawędzie jednego drzewa można podzielić w unikalny sposób na dwa podgrafy, z których jeden jest cyklem, a drugi lasem, tak że każde drzewo lasu zawiera dokładnie jeden wierzchołek cyklu.

Zbadano również niektóre bardziej specyficzne typy pseudolasów.

1 las , czasami nazywany ilość pseudoforest , jest pseudoforest do których nie więcej krawędzi można dodawać bez powodowania jakiś składnik wykresu zawiera wiele cykli. Jeśli pseudolas zawiera drzewo jako jeden ze swoich składników, nie może być lasem 1, ponieważ można dodać albo krawędź łączącą dwa wierzchołki w obrębie tego drzewa, tworząc pojedynczy cykl, albo krawędź łączącą to drzewo z innym składnikiem. Tak więc lasy 1 są dokładnie tymi pseudolasami, w których każdy składnik jest drzewem 1.

W obejmujących pseudoforests z wykresu na nieukierunkowane G są pseudoforest subgraphs z G , które posiadają wszystkie wierzchołki G . Taki pseudolas nie musi mieć żadnych krawędzi, bo np. podgraf, który ma wszystkie wierzchołki G i nie ma żadnych krawędzi, jest pseudolasem (którego składowymi są drzewa składające się z jednego wierzchołka).

Te maksymalne pseudoforests z G są pseudoforest subgraphs z G , które nie są zawarte w dowolnej większej pseudoforest o G . Maksymalny pseudolas G jest zawsze pseudolasem obejmującym, ale nie odwrotnie. Jeśli G nie ma połączonych komponentów, które są drzewami, to jego maksymalne pseudolasy są 1-lasami, ale jeśli G ma komponent drzewa, jego maksymalne pseudolasy nie są 1-lasami. Mówiąc precyzyjnie, w każdym grafie G jego maksymalne pseudolasy składają się z każdego składowego drzewa G , wraz z jednym lub więcej rozłącznymi 1-drzewami pokrywającymi pozostałe wierzchołki G .

Kierowane pseudolasy

Wersje tych definicji są również używane dla grafów skierowanych . Podobnie jak graf nieskierowany, graf skierowany składa się z wierzchołków i krawędzi, ale każda krawędź jest skierowana od jednego ze swoich punktów końcowych do drugiego punktu końcowego. Skierowane pseudoforest jest skierowany wykres, w którym każdy wierzchołek ma co najwyżej jedną krawędź wychodzącą; to znaczy, że ma co najwyżej jeden stopień . Skierowany 1-lasów - powszechnie zwany wykres funkcjonalny (patrz poniżej ), czasami ilość kierowany pseudoforest - wykres jest skierowany w którym każdy wierzchołek ma outdegree dokładnie jeden. Jeśli D jest pseudolasem ukierunkowanym, graf nieskierowany utworzony przez usunięcie kierunku z każdej krawędzi D jest pseudolasem nieskierowanym.

Liczba krawędzi

Każdy pseudolas na zbiorze n wierzchołków ma najwyżej n krawędzi, a każdy maksymalny pseudolas na zbiorze n wierzchołków ma dokładnie n krawędzi. I odwrotnie, jeśli wykres G ma tę właściwość, że dla każdego podzbioru S ma na swoich wierzchołkach, to liczba krawędzi w indukowanej podgrafu z S jest najwyżej liczba wierzchołków S , a G jest pseudoforest. 1-drzewa można zdefiniować jako połączone grafy z równą liczbą wierzchołków i krawędzi.

Przechodząc od pojedynczych grafów do rodzin grafów, jeśli rodzina grafów ma tę właściwość, że każdy podgraf w rodzinie jest również w rodzinie, a każdy graf w rodzinie ma co najwyżej tyle krawędzi co wierzchołki, to rodzina zawiera tylko pseudolasy. Na przykład każdy podwykres węży (wykres narysowany w taki sposób, że każda para krawędzi ma jeden punkt przecięcia) jest również wężem, więc przypuszczenie Conwaya, że każda wąska linia ma co najwyżej tyle krawędzi, ile wierzchołków, można powtórzyć, mówiąc, że każdy thrackle to pseudolas. Bardziej precyzyjna charakterystyka jest taka, że ​​jeśli przypuszczenie jest prawdziwe, to drążki są dokładnie pseudolasami bez cyklu czterech wierzchołków i co najwyżej jednego cyklu nieparzystego.

Streinu i Theran uogólniają warunki rzadkości definiujące pseudolasy: definiują graf jako ( k , l )-rzadki, jeśli każdy niepusty podgraf z n wierzchołkami ma co najwyżej kn  −  l krawędzi, a ( k , l )-ciasny, jeśli jest ( k , l )-rzadki i ma dokładnie kn  −  l krawędzi. Zatem pseudolasy są grafami (1,0)-rzadkimi, a maksymalne pseudolasy są grafami (1,0)-ciasnymi. Kilka innych ważnych rodzin grafów można zdefiniować na podstawie innych wartości k i l , a gdy l  ≤  k grafy ( k , l )-rzadkie można scharakteryzować jako grafy utworzone jako połączenie krawędzi i rozłącznego l lasów i k  −  l pseudolasy.

Prawie każdy wystarczająco rzadki graf losowy jest pseudolasem. Oznacza to, że jeśli c jest stałą z 0 < c < 1/2, a P _c ( n ) jest prawdopodobieństwem, że wybieranie jednostajnie losowe spośród n- wierzchołkowych grafów z cn krawędziami skutkuje powstaniem pseudolasu, wtedy P _c ( n ) dąży do jednego w limicie dla dużych n . Jednak dla c > 1/2 prawie każdy graf losowy z krawędziami cn ma dużą składową, która nie jest jednocykliczna.

Wyliczenie

Wykres jest prosty, jeśli nie ma własnych pętli ani wielu krawędzi z tymi samymi punktami końcowymi. Liczba prostych 1-drzew z n oznaczonymi wierzchołkami wynosi

${\ Displaystyle n \ suma _ {k = 1} ^ {n} {\ Frac {(-1) ^ {k-1}} {k}} \ suma _ {n_ {1} + \ cdots + n_ {k }=n}{\frac {n!}{n_{1}!\cdots n_{k}!}}{\binom {{\binom {n_{1}}{2}}+\cdots +{\binom {n_{k}}{2}}}{n}}.}$

Wartości n do 300 można znaleźć w sekwencji OEIS :  A057500 z on-line z Encyklopedii Integer sekwencji .

Liczba maksymalnie skierowanych pseudolasów na n wierzchołkach, umożliwiających pętle własne, wynosi n ⁿ , ponieważ dla każdego wierzchołka istnieje n możliwych punktów końcowych dla krawędzi wychodzącej. Andre Joyal użył tego dostarczenie bijective dowód o wzorze Cayley jest , że liczba nieukierunkowane drzew na n węzłów n ^{n  - 2} , poprzez znalezienie bijection między maksymalnymi skierowane pseudoforests i nieukierunkowane drzew z dwóch oddzielnych węzłów. Jeśli pętle własne nie są dozwolone, liczba maksymalnie skierowanych pseudolasów wynosi ( n  − 1) ⁿ .

Wykresy funkcji

Funkcja ze zbioru {0,1,2,3,4,5,6,7,8} do siebie i odpowiadający jej wykres funkcyjny

Kierowane pseudolasy i endofunkcje są w pewnym sensie matematycznie równoważne. Każda funkcja ƒ ze zbioru X do siebie (to jest do endomorfizm z X ) mogą być interpretowane jako określające skierowany pseudoforest która ma krawędź od X do Y , gdy ƒ ( x ) = y . Wynikowy pseudolas ukierunkowany jest maksymalny i może zawierać pętle własne, gdy jakaś wartość x ma ƒ( x ) = x . Alternatywnie, pominięcie pętli własnych tworzy niemaksymalny pseudolas. W przeciwnym kierunku, każdy maksymalnie skierowany pseudolas określa funkcję ƒ taką, że ƒ( x ) jest celem krawędzi wychodzącej z x , a każdy niemaksymalnie skierowany pseudolas może zostać ustawiony na maksymalny przez dodanie własnych pętli, a następnie przekonwertowany w funkcję w ten sam sposób. Z tego powodu maksymalnie ukierunkowane pseudolasy są czasami nazywane grafami funkcjonalnymi . Postrzeganie funkcji jako grafu funkcjonalnego zapewnia wygodny język do opisywania właściwości, które nie są tak łatwe do opisania z punktu widzenia teorii funkcji; technika ta ma szczególne zastosowanie do problemów związanych z funkcjami iterowanymi , które odpowiadają ścieżkom w grafach funkcjonalnych.

Wykrywanie cyklu , problem podążania ścieżką w grafie funkcjonalnym w celu znalezienia w nim cyklu, ma zastosowanie w kryptografii i obliczeniowej teorii liczb , jako część algorytmu rho Pollarda do faktoryzacji liczb całkowitych oraz jako metoda znajdowania kolizji w kryptograficznych funkcjach mieszających . W tych aplikacjach oczekuje się, że ƒ będzie zachowywać się losowo; Flajolet i Odlyzko badają teoretyczne właściwości grafów funkcjonalnych grafów wynikających z losowo wybranych odwzorowań. W szczególności postać paradoksu urodzinowego implikuje, że w losowym grafie funkcjonalnym z n wierzchołkami ścieżka rozpoczynająca się od losowo wybranego wierzchołka zazwyczaj zapętla się z powrotem, tworząc cykl w ramach O ( √ n ) kroków. Konyagin i in. poczynili postępy analityczne i obliczeniowe w statystykach wykresów.

Martin, Odlyzko i Wolfram badają pseudolasy , które modelują dynamikę automatów komórkowych . Te grafy funkcyjne, które nazywają diagramami przejść stanów , mają jeden wierzchołek dla każdej możliwej konfiguracji, w jakiej może znajdować się zespół komórek automatu, oraz krawędź łączącą każdą konfigurację z konfiguracją, która następuje po niej zgodnie z regułą automatu. Ze struktury tych diagramów można wywnioskować właściwości automatu, takie jak liczba składowych, długość cykli granicznych, głębokość drzew łączących stany nieograniczające z tymi cyklami, czy symetrie diagramu. Na przykład, każdy wierzchołek bez przychodzącej krawędzi odpowiada wzorowi Garden of Eden, a wierzchołek z samopętlą odpowiada wzorowi martwej natury .

Kolejne wczesne zastosowanie grafów funkcjonalnych dotyczy pociągów używanych do badania układów potrójnych Steinera . Ciąg systemu potrójnego jest wykresem funkcjonalnym mającym wierzchołek dla każdej możliwej trójki symboli; każda trójka pqr jest odwzorowana przez ƒ na stu , gdzie pqs , prt i qru są trójkami należącymi do układu trójkowego i zawierającymi odpowiednio pary pq , pr i qr . Wykazano, że pociągi są potężnym niezmiennikiem systemów potrójnych, chociaż są nieco kłopotliwe w obliczeniach.

Matroid dwukołowy

Matroid jest strukturą matematyczną w której niektóre elementy są zestawy określa się niezależnie , w taki sposób, że niezależne zestawy spełniają właściwości wzorowane właściwości liniowa niezależność w przestrzeni wektorowej . Jednym ze standardowych przykładów matroidu jest matroid graficzny, w którym niezależne zbiory są zbiorami krawędzi w lasach grafu; Matroidalna struktura lasów jest ważna w algorytmach obliczania minimalnego drzewa opinającego grafu. Analogicznie możemy zdefiniować matroidy z pseudolasów.

Dla dowolnego grafu G = ( V , E ) możemy zdefiniować matroid na krawędziach G , w którym zbiór krawędzi jest niezależny wtedy i tylko wtedy, gdy tworzy pseudolas; ten matroid jest znany jako dwukołowy matroid (lub matroid rowerowy ) G . Najmniejszymi zbiorami zależnymi dla tego matroidu są minimalne połączone podgrafy G, które mają więcej niż jeden cykl, a te podgrafy są czasami nazywane rowerami. Istnieją trzy możliwe typy rowerów: wykres theta ma dwa wierzchołki, które są połączone trzema wewnętrznie rozłącznymi ścieżkami, wykres ósemkowy składa się z dwóch cykli mających wspólny wierzchołek, a wykres kajdanek składa się z dwóch rozłącznych cykli połączonych ścieżką . Wykres jest pseudolasem wtedy i tylko wtedy, gdy nie zawiera roweru jako podgrafu.

Zakazane osoby nieletnie

Wykres motyl (z lewej) i wykres diament (z prawej), Zakazane nieletni dla pseudoforests

Utworzenie drugorzędnego pseudolasu poprzez zawężenie niektórych jego krawędzi i usunięcie innych tworzy kolejny pseudolas. Zatem rodzina pseudolasów jest zamknięta pod podrzędnymi, a twierdzenie Robertsona-Seymoura implikuje, że pseudolasy można scharakteryzować w kategoriach skończonego zbioru zabronionych podrzędnych , analogicznie do twierdzenia Wagnera charakteryzującego grafy planarne jako grafy bez pełnego grafu K ₅ ani pełnego dwudzielnego wykresu K _3,3 jako nieletnich. Jak omówiono powyżej, każdy wykres nie-pseudolasu zawiera jako podgraf kajdanki, ryc. 8 lub wykres theta; każdy wykres kajdanek lub wykres z ryciny 8 może zostać skrócony w celu utworzenia wykresu motylkowego (rysunek z pięcioma wierzchołkami), a każdy wykres theta może zostać skrócony, aby utworzyć wykres rombowy (wykres teta z czterema wierzchołkami), więc każdy nie-pseudolas zawiera albo motyla lub diamentu jako nieletniego, i są to jedyne grafy minorowe niebędące grafami pseudoleśnymi. Tak więc graf jest pseudolasem wtedy i tylko wtedy, gdy nie ma w nim motyla lub diamentu jako nieletniego. Jeśli zabronimy tylko diamentu, ale nie motyla, uzyskana większa rodzina wykresów składa się z wykresów kaktusowych i rozłącznych związków wielu wykresów kaktusowych.

Mówiąc prościej, jeśli weźmiemy pod uwagę multigrafy z pętlami własnymi , istnieje tylko jeden zabroniony drugorzędny, wierzchołek z dwiema pętlami.

Algorytmy

Wczesne zastosowanie pseudolasów w algorytmie obejmuje algorytm sieciowy simplex i jego zastosowanie do uogólnionych problemów przepływowych modelujących konwersję między towarami różnych typów. W tych problemach jako dane wejściowe podaje się sieć przepływu, w której wierzchołki modelują każdy towar, a krawędzie modelują dopuszczalne konwersje między jednym towarem a drugim. Każda krawędź jest oznaczona pojemnością (ile towaru można przekonwertować w jednostce czasu), mnożnikiem przepływu (współczynnikiem konwersji między towarami) oraz kosztem (ile straty lub, jeśli jest ujemny, zysku jest ponoszone na jednostkę konwersja). Zadanie polega na określeniu, jaka część każdego towaru ma zostać przekonwertowana przez każdą krawędź sieci przepływu, aby zminimalizować koszty lub zmaksymalizować zysk, przy jednoczesnym przestrzeganiu ograniczeń przepustowości i nie dopuszczaniu do gromadzenia się niewykorzystanych towarów dowolnego rodzaju. Tego typu problem można sformułować w postaci programu liniowego i rozwiązać za pomocą algorytmu simplex . Rozwiązania pośrednie wynikające z tego algorytmu, jak również ostateczne rozwiązanie optymalne, mają specjalną strukturę: każda krawędź w sieci wejściowej jest albo niewykorzystana, albo wykorzystana w pełni, z wyjątkiem podzbioru krawędzi, tworzących rozpinający się pseudolas sieć wejściowa, dla której wielkości przepływu mogą leżeć od zera do pełnej przepustowości. W tej aplikacji grafy jednocykliczne są również czasami nazywane drzewami rozszerzonymi, a maksymalne pseudolasy są również czasami nazywane rozszerzonymi lasami .

Problem minimalnego pseudolasu obejmuje znalezienie opinającego pseudolasu o minimalnej wadze w większym grafie ważonym krawędziowo G . Ze względu na matroidalną strukturę pseudolasów, pseudolasy o minimalnej wadze i maksymalnej masie można znaleźć za pomocą zachłannych algorytmów podobnych do tych dla problemu minimalnego drzewa opinającego. Jednak Gabow i Tarjan znaleźli w tym przypadku bardziej wydajne podejście oparte na czasie liniowym.

Pseudoarboricity grafu G są zdefiniowane analogicznie do arboricity jako minimalna liczba pseudoforests, w którym jego krawędzie mogą być podzielone; równoważnie, jest to minimum k takie, że G jest ( k ,0)-rzadkie, lub minimum k takie, że krawędzie G mogą być zorientowane tak, aby tworzyły skierowany graf o co najwyżej k stopniach zewnętrznych . Ze względu na matroidalną strukturę pseudolasów pseudoarboryczność można obliczyć w czasie wielomianowym.

Losowo wykres dwudzielna z n wierzchołków z obu stron jej bipartition, i CN krawędzie niezależnie wybrane losowo z każdej z n ² możliwych par wierzchołkach, to z dużym prawdopodobieństwem pseudoforest gdy c jest stałą bezwarunkowo mniejszy niż jeden. Fakt ten odgrywa kluczową rolę w analizie haszowania kukułkowego , struktury danych do wyszukiwania par klucz-wartość poprzez przeszukiwanie jednej z dwóch tabel mieszających w lokalizacjach określonych na podstawie klucza: można utworzyć wykres, „wykres kukułkowy”, których wierzchołki odpowiadają lokalizacjom tablicy mieszającej i których krawędzie łączą dwie lokalizacje, w których można znaleźć jeden z kluczy, a algorytm mieszania z kukułką udaje się znaleźć lokalizacje dla wszystkich swoich kluczy wtedy i tylko wtedy, gdy graf kukułkowy jest pseudolasem.

Pseudoforests również odgrywać kluczową rolę w równoległych algorytmów do kolorowania grafów i związanych z tym problemów.

Uwagi

Bibliografia

Zewnętrzne linki

• Weisstein, Eric W. , "Wykres jednocykliczny" , MathWorld