Qrafiklər və ŞəbəkələrPlanar Qrafiklər
Budur, grafika nəzəriyyəsi ilə əlaqəli başqa bir tapmacadır.
Kiçik bir kənddə su, elektrik və qaz istehsal edən üç ev və üç köməkçi zavod var. Kursların hər birini kommunal zavodların hər birinə bağlamalıyıq, ancaq kəndin yerləşməsi səbəbindən fərqli borular və kabellərin keçməsinə icazə verilmir.
Evlərin hər birini xəttlərinizin heç biri kəsişmədən aşağıdakı kommunal şirkətlərə bağlamağa çalışın:
Əvvəllər Königsberg körpüləri kimi tez bir zamanda bu problemin də mümkün olmadığını aşkar edirsiniz. Bəzi qrafların kənarları üst-üstə düşmədən tərtib edilə biləcəyi görünür - bunlara planar qrafiklər deyilir - amma digərləri bilməz.
Üç kommunal tapmacanın içindəki
Planarallıq
Bu planar qrafikdir, amma
Euler Formulu
Bütün planar qrafiklər çəkdikləri təyyarəni üzlər adlanan bir sıra bölgələrə bölürlər.
11 Vertices + Üzlər
15 Vertices + Üzlər
25 Vertices + Üzlər
Bu nömrələri müqayisə edərkən, kənarların sayının həmişə
Təəssüf ki, sonsuz sayda qrafik var və Euler tənliyinin işlədiyini görmək üçün hər birini yoxlaya bilmirik. Bunun əvəzinə hər hansı bir qrafik üçün işləyən sadə bir
F | V | E |
0 | 1 | 0 |
0 + 1 = 0 + 1
Hər hansı bir (sonlu) bir qrafik bir vertexdən başlayaraq və daha çox ucu bir-bir əlavə etməklə inşa edilə bilər. Biz göstərdik ki, hansı yeni nöqtələr əlavə etsək də, Euler tənliyi doğrudur. Buna görə bütün qrafiklər üçün etibarlıdır.
İstifadə etdiyimiz prosesə riyazi induksiya deyilir. Sadə nəticələrdən başlayaraq və daha mürəkkəb işlərin qurulması zamanı nəticənin hər addımda dayandığını göstərmək üçün sonsuz sayda nəticəni sübut etmək üçün çox faydalıdır.
Bir çox planar qrafiklər


Bu, Euler düsturundan yalnız plan qrafikləri üçün deyil, bütün polyhedra üçün istifadə edə biləcəyimiz deməkdir - bir kiçik fərqlə. Polyedra qrafikə çevrilərkən üzlərdən biri yox olur: polyhedranın ən üst üzü "kənar" olur; qrafiklərdən.
Başqa sözlə, sayını sayırsan kənarları , üzlər və Hər hansı bir polyhedron təpə, siz ki, tapa bilərsiniz F + V = E +
Icosahedron
20 üz
12 Vertices
30 kənarları
Rhombicosidodecahedron
62 üzlər
60 Vertices
120 kənarları
Kəsilmiş Icosahedron
32 Üz (12 qara, 20 ağ)
60 Vertices
90 kənarları