Planārs grafs

Vikipēdijas raksts
Pārlēkt uz: navigācija, meklēt

Planārs grafs ir jebkurš grafs, ko ir iespējams attēlot plaknē tā, ka tā šķautnes nekrustojas. Planāru grafu, kas attēlots plaknē bez šķautņu krustošanās, sauc par plakanu grafu.

Ar noteiktas projekcijas palīdzību (ko sauc par stereogrāfisko projekciju) var pierādīt, ka grafu plaknē var attēlot bez šķautņu krustošanās tad un tikai tad, kad to var attēlot uz sfēras bez šķautņu krustošanās.

Piemēri[izmainīt šo sadaļu | labot pirmkodu]

Planāri grafi ir, piemēram, jebkurš koks, pilnie grafi K3, K4, jebkurš cikla grafs utt. Planāri nav pilnais grafs K5, Pētersena grafs utt.

Teorēma[izmainīt šo sadaļu | labot pirmkodu]

Attiecībā uz planāriem grafiem ir svarīga šāda teorēma: Ja planāram grafam ir n \geq 3 virsotnes, tad tam nav vairāk kā 3n - 6 šķautnes.

Skatīt arī[izmainīt šo sadaļu | labot pirmkodu]