Akt iqtisodiyot va menedjment

Kuratovskiy va Vagner teoremalari

The Polsha matematik Kazimierz Kuratovskiy jihatidan planar grafikalar xarakteristikasini taqdim etdi taqiqlangan grafikalar, endi sifatida tanilgan Kuratovskiy teoremasi:
A cheklangan grafik planar hisoblanadi agar va faqat agar unda a mavjud emas subgraf bu bo'linish ning to'liq grafik K₅ yoki to'liq ikki tomonlama grafik  (yordam dasturi ).
A bo'linish grafika vertikallarni qirralarga kiritish natijasida hosil bo'ladi (masalan, qirrani • —— • nolga • - • - • ga o'zgartirish) nol yoki undan ko'p marta.

Yo'q bilan grafikaga misol K₅ yoki K_3,3 subgraf. Biroq, uning tarkibiga kiradi K_3,3 va shuning uchun tekis emas.
Bo'limlarni ko'rib chiqish o'rniga, Vagner teoremasi bilan shug'ullanadi voyaga etmaganlar:
Cheklangan grafik tekislikdadir, agar u yo'q bo'lsa  yoki  kabi voyaga etmagan.
A voyaga etmagan grafika subgrafani olish va tepalikka bir necha marta qisqartirish natijasida hosil bo'ladi, asl uchlarning har bir qo'shnisi yangi tepaga qo'shni bo'lib qoladi.

Ekanligini ko'rsatuvchi animatsiya Petersen grafigi K ga oz izomorfik kiradi_3,3 grafigi va shuning uchun tekis bo'lmagan
Klaus Vagner grafiklarning biron bir kichik yopiq klassi cheklangan "taqiqlangan voyaga etmaganlar "Bu endi Robertson-Seymur teoremasi, uzoq hujjatlar qatorida isbotlangan. Ushbu teorema tilida  va  cheklangan planar grafikalar sinfi uchun taqiqlangan voyaga etmaganlardir.

Planarlikning boshqa mezonlari

Amalda, Beratovskiy kriteriyasidan foydalanib, berilgan grafikning tekis bo'lishini tezda hal qilish qiyin. Biroq, tez mavjud algoritmlar ushbu muammo uchun: bilan grafik uchun n tepaliklarni o'z vaqtida aniqlash mumkin O (n) (chiziqli vaqt) grafik tekis bo'ladimi yoki yo'qmi (qarang planariyani sinash ).

Bilan oddiy, bog'langan, planar grafik uchun v tepaliklar va e qirralarning va f yuzlari, quyidagi oddiy shartlar bajarilishi kerak v ≥ 3:

• 
  Teorema 1. e ≤ 3v − 6;
  
• 
  Teorema 2. Agar 3 uzunlikdagi tsikllar bo'lmasa, u holda e ≤ 2v − 4.
  
• 
  Teorema 3. f ≤ 2v − 4.
  

Shu ma'noda, planar grafikalar siyrak grafikalar ularda faqat O (v) qirralar, asimptotik ravishda maksimal O dan kichik (v²). Grafik K_3,3Masalan, 6 ta tepalikka, 9 ta qirraga ega va 3 uzunlik tsikllari yo'q. Shuning uchun 2-teorema bo'yicha u tekis bo'lishi mumkin emas. Ushbu teoremalar planaritatsiya uchun etarli shart bo'lmagan zaruriy shartlarni taqdim etadi va shu sababli grafika tekislik emasligini emas, balki uning tekisligini isbotlash uchungina ishlatilishi mumkin. Agar ikkala teorema 1 va 2 bajarilmasa, boshqa usullardan foydalanish mumkin.

Planar grafik zichligi

Zichlik  planar grafika yoki tarmoq, qirralar sonining nisbati sifatida aniqlanadi  bilan tarmoqdagi mumkin bo'lgan qirralarning soniga  planar grafik orqali berilgan tugunlar  , berib  . To'liq siyrak grafika mavjud  , muqobil ravishda butunlay zich planar grafik mavjud