Gabriel graf

Gabriel-grafen med 100 slumpmässiga punkter

Punkterna $a$ och $b$ är Gabriel-grannar, eftersom $c$ är utanför deras diametercirkel.

Närvaron av punkt $c$ i cirkeln förhindrar punkterna $a$ och $b$ från att vara Gabriel-grannar.

Inom matematik och beräkningsgeometri uttrycker Gabriel -grafen för en uppsättning $S$ av punkter i det euklidiska planet en föreställning om närhet eller närhet till dessa punkter. Formellt är det grafen $G$ med vertexuppsättningen $S$ där två distinkta punkter $p\in S$ och $q\in S$ är intilliggande exakt när den slutna skivan som har $pq$ som diameter inte innehåller några andra punkter. Ett annat sätt att uttrycka samma närliggande kriterium är att $p$ och $q$ ska vara de två närmaste givna punkterna till deras mittpunkt , utan att någon annan given punkt är lika nära. Gabriel-grafer generaliserar naturligtvis till högre dimensioner, med de tomma skivorna ersatta av tomma slutna bollar . Gabriel-grafer är uppkallade efter K. Ruben Gabriel , som introducerade dem i en tidning med Robert R. Sokal 1969.

Perkolering

För Gabriel-grafer av oändliga slumpmässiga punktuppsättningar, ger den finita platsperkolationströskeln den bråkdel av punkter som behövs för att stödja anslutning: om en slumpmässig delmängd med färre hörn än tröskeln ges, kommer den återstående grafen nästan säkert att ha endast ändliga anslutna komponenter, medan om storleken på den slumpmässiga delmängden är mer än tröskeln, kommer den återstående grafen nästan säkert att ha en oändlig komponent (liksom ändliga komponenter). Detta tröskelvärde visades existera av Bertin, Billiot & Drouilhet (2002), och mer exakta värden för både plats- och obligationströsklar har givits av Norrenbrock.

Relaterade geometriska grafer

Gabriel-grafen är en subgraf av Delaunay-trianguleringen . Den kan hittas i linjär tid om Delaunay-trianguleringen ges.

Gabriel-grafen innehåller, som undergrafer, det euklidiska minimumspännande trädet , grafen för relativ grannskap och grafen för närmaste granne .

Det är en instans av ett beta-skelett . Liksom beta-skelett, och till skillnad från Delaunay-triangulering, är det inte en geometrisk skiftnyckel : för vissa punktuppsättningar kan avstånden inom Gabriel-grafen vara mycket större än de euklidiska avstånden mellan punkter.