Tasandiline graaf

Allikas: Vikipeedia
Graafide näited
Tasandiline Mittetasandiline
Butterfly graph.svg
Liblik-graaf
Complete graph K5.svg
K5
CGK4PLN.svg
Täisgraaf
K4 on tasandiline
Biclique K 3 3.svg
K3,3

Tasandiline graaf ehk planaarne graaf on graaf, mida on võimalik tasandile joonistada nii, et tema servad väljaspool tippe ei lõikuks.

Tasandisust ehk planaarsust on võimalik mitmel viisil ka rangelt defineerida [1].

Tasandilise graafi tippude ümberpaigutamisega võib seda kujutada ka mittetasandilisena. Graafi tasandilisuse tingimused on esitatud Kuratovski, Pontrjagin-Kuratovski ja Wagneri teoreemide näol.


Viide[muuda | redigeeri lähteteksti]

  1. A. Buldas, P. Laud, J. Villemson. 2003 Graafid. Tartu, ISBN 9789949118182