Graf planar

De la Wikipedia, enciclopedia liberă
Jump to navigation Jump to search
Grafuri de exemplificare
Planar Neplanar
Butterfly graph.svg

Graful fluture⁠(d)

Complete graph K5.svg

Graful complet K5

CGK4PLN.svg

Graful complet
K4

Biclique K 3 3.svg

Graful utilitar⁠(d) K3,3

În teoria grafurilor, un graf planar este un graf care poate fi încorporat într-un plan, adică poate fi trasat în plan în așa fel încât marginile sale să se intersecteze doar în noduri. Cu alte cuvinte, acesta poate fi desenat în așa fel încât oricare două muchii să nu se intersecteze.[1] Un astfel de desen este numit un graf în plan sau o încorporare în plan a grafului. Un graf în plan poate fi definit ca un graf planar cu o funcție de corespondență de la fiecare nod la un punct din plan, și de la fiecare muchie la o curbă plană în planul respectiv, astfel încât punctele extreme ale fiecărei curbe să fie punctele corespondente nodurilor de la capăt, și ca toate curbele să fie disjuncte, cu excepția extremităților lor.

Toate grafurile care pot fi trasate într-un plan pot fi trasate și pe sferă, și vice-versa.

Grafurile în plan pot fi codificate prin aplicații combinatorice⁠(d).

Clasa de echivalență a reprezentărilor topologic echivalente de pe sferă se numește aplicație planară. Deși un graf în plan are o față externă, sau nemărginită, niciuna dintre fețele unei aplicații planare nu are statut special.

Grafurile planare se pot generaliza la grafurile desenabile pe o suprafață de un anumit gen⁠(d). În această terminologie, grafurile planare au genul⁠(d) 0, deoarece planul (și sfera) sunt suprafețe de genul 0.

Note[modificare | modificare sursă]

  1. ^ Trudeau, Richard J. (1993). Introduction to Graph Theory (ed. Corrected, enlarged republication.). New York: Dover Pub.. pp. 64. ISBN 978-0-486-67870-2. http://store.doverpublications.com/0486678709.html. Accesat la 8 august 2012. „Thus a planar graph, when drawn on a flat surface, either has no edge-crossings or can be redrawn without them.”
     

Referințe[modificare | modificare sursă]

  • Kuratowski, Kazimierz (1930), „Sur le problème des courbes gauches en topologie” (în French), Fundamenta Mathematicae 15: 271–283, http://matwbn.icm.edu.pl/ksiazki/fm/fm15/fm15126.pdf
     .
  • Wagner, K. (), „Über eine Eigenschaft der ebenen Komplexe”, Mathematische Annalen (în German), 114: 570–590, doi:10.1007/BF01594196  Mai multe valori specificate pentru |DOI= și |doi= (ajutor).
  • Boyer, John M.; Myrvold, Wendy J. (), „On the cutting edge: Simplified O(n) planarity by edge addition” (PDF), Journal of Graph Algorithms and Applications⁠(d), 8 (3): 241–273, doi:10.7155/jgaa.00091  Mai multe valori specificate pentru |DOI= și |doi= (ajutor).
  • McKay, Brendan; Brinkmann, Gunnar, A useful planar graph generator .
  • de Fraysseix, H.; Ossona de Mendez, P.; Rosenstiehl, P. (), „Trémaux trees and planarity”, International Journal of Foundations of Computer Science, 17 (5): 1017–1029, doi:10.1142/S0129054106004248  Mai multe valori specificate pentru |DOI= și |doi= (ajutor). Ediție specială pe Grafic Desen.
  • D. A. Bader și S. Sreshta, Un Nou Algoritm Paralel pentru Planeitate de Testare, UNM-ECE Raport Tehnic 03-002, octombrie 1, 2003.
  • Fisk, Steve (), „A short proof of Chvátal's watchman theorem”, Journal of Combinatorial Theory, Series B, 24 (3): 374, doi:10.1016/0095-8956(78)90059-X  Mai multe valori specificate pentru |DOI= și |doi= (ajutor).