Graf Gabriel

Graf Gabriel al 100 de puncte aleatorii

Format:Imagine multiplă În matematică și Format:Ill-wd, graful Gabriel al unei mulțimi Format:Mvar de puncte din planul euclidian exprimă o noțiune de apropiere a acelor puncte. Formal, este graful $G$ cu mulțimea de noduri Format:Mvar în care oricare două puncte distincte $p\in S$ și $q\in S$ sunt considerate adiacente atunci când discul închis având $pq$ drept diametru nu conține alte puncte din Format:Mvar. Un alt mod de a exprima același criteriu de adiacență este acela că $p$ și $q$ ar trebui să fie cele două puncte date cele mai apropiate de punctul lor de mijloc, fără ca vreun alt punct dat să fie la fel de apropiat. Grafurile Gabriel se generalizează în mod natural pentru dimensiuni mai mari, cu discurile înlocuite cu bile închise. Grafurile Gabriel sunt denumite după K. Ruben Gabriel, care le-a prezentat într-o lucrare împreună cu Robert R. Sokal în 1969.

Percolare

Pentru grafurile Gabriel ale mulțimilor infinite de puncte, Format:Ill-wd este fracția de puncte necesară pentru a susține conectivitatea: dacă se dă o submulțime aleatorie cu mai puține noduri decât pragul, graful rămas va avea aproape sigur doar un număr finit de noduri conectate, iar dacă dimensiunea submulțimii aleatorie este mai mare decât pragul, atunci graful rămas va avea aproape sigur o componentă infinită (precum și componente finite). S-a demonstrat că acest prag există de către Bertin, Billiot și Drouilhet în 2002, iar valori mai precise au fost date de Norrenbrock.

Grafuri geometrice înrudite

Un graf Gabriel este un subgraf al triangulării Delaunay. El poate fi obținut în timp liniar din triangularea Delaunay.

Graful Gabriel conține, ca subgrafuri, Format:Ill-wd, graful de vecinătate relativă și graful celor mai apropiați vecini.