Wykres Gabriela
W matematyce i geometrii obliczeniowej Gabriela zbioru punktów na płaszczyźnie euklidesowej wyraża jedno pojęcie bliskości lub tych punktów . Formalnie jest to wykres z zestawem wierzchołków w którym dowolne dwa różne punkty sąsiadują dokładnie, gdy zamknięty dysk mający średnicę średnicę zawiera innych punktów Innym sposobem wyrażenia tego samego kryterium sąsiedztwa jest to, że być ich punktu środkowego , przy czym żaden inny dany punkt nie jest tak blisko. Wykresy Gabriela w naturalny sposób uogólniają się na wyższe wymiary, z pustymi dyskami zastąpionymi pustymi zamkniętymi kulkami . Grafy Gabriela zostały nazwane na cześć K. Rubena Gabriela , który przedstawił je w artykule z Robertem R. Sokalem w 1969 roku.
Przesiąkanie
W przypadku grafów Gabriela nieskończonych losowych zestawów punktów próg perkolacji skończonych miejsc daje ułamek punktów potrzebnych do obsługi łączności: jeśli podany jest losowy podzbiór o mniejszej liczbie wierzchołków niż próg, pozostały graf prawie na pewno będzie miał tylko skończone połączone komponenty, podczas gdy jeśli rozmiar losowego podzbioru jest większy niż próg, to pozostały wykres prawie na pewno będzie miał nieskończoną składową (jak również skończone składowe). Próg ten został udowodniony przez Bertina, Billiota i Drouilheta (2002) , a dokładniejsze wartości zarówno progów miejsc, jak i wiązań zostały podane przez Norrenbrocka.
Powiązane wykresy geometryczne
Wykres Gabriela jest podgrafem triangulacji Delaunaya . Można go znaleźć w czasie liniowym , jeśli podana jest triangulacja Delaunaya.
Graf Gabriela zawiera, jako podgrafy, euklidesowe minimalne drzewo rozpinające , graf względnego sąsiedztwa i graf najbliższego sąsiada .
Jest to przykład beta-szkieletu . Podobnie jak beta-szkielety iw przeciwieństwie do triangulacji Delaunaya, nie jest to klucz geometryczny : w przypadku niektórych zestawów punktów odległości na wykresie Gabriela mogą być znacznie większe niż odległości euklidesowe między punktami.