Qrafiklər və ŞəbəkələrPlanar Qrafiklər

Bu səhifə avtomatik tərcümə edildi və səhvlər ola bilər. Zəhmət olmasa tərcümələri nəzərdən keçirməyə kömək etmək istəyirsinizsə əlaqə qurun!

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.

K3 planar.

K4 .

K5 .

Tam qrafik K5 planar olmayan ən kiçik qrafikdir. Tərkibində olan hər hansı digər qrafik K5 bir şəkildə bir alt yazı da planar deyil. Bura daxildir K6 , K7 və bütün daha böyük qrafiklər.

Üç kommunal tapmacanın içindəki qrafik ikitərəfli qrafikdir K3,3 . Məlum olur ki, hər hansı bir planar olmayan qrafada ya a olmalıdır K5 və ya a K3,3 (və ya bu iki qrafikin bir bölməsi ) alt şəkil kimi. Buna Kuratowski teoremi deyilir.

Planarallıq

Bu planar qrafikdir, amma ${n} dik nöqtələr bükülmüşdür. Dikləri düzəldin ki, kənarların heç biri üst-üstə düşməsin.

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.

Vertices
üzlər
kənarları
11 Vertices + Üzlər

Vertices
üzlər
kənarları
15 Vertices + Üzlər

Vertices
üzlər
kənarları
25 Vertices + Üzlər

Bu nömrələri müqayisə edərkən, kənarların sayının həmişə olduğunu görəcəksiniz üzlərin sayı üstə də ucların sayından . Başqa sözlə, F + V = E + 1. Bu nəticə Euler tənliyi adlanır və Königsberg Körpülər problemini həll edən eyni riyaziyyatçının adını daşıyır.

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 sübut tapmağa çalışa bilərik ...

0 + 1 = 0 + 1

The simplest graph consists of a single vertex. We can easily check that Euler’s equation works.

Let us add a new vertex to our graph. We also have to add an edge, and Euler’s equation still works.

If we want to add a third vertex to the graph we have two possibilities. We could create a small triangle: this adds one vertex, one face and two edges, so Euler’s equation still works.

Instead we could simply extend the line by one: this adds one vertex and one edge, and Euler’s equation works.

Let’s keep going: if we now create a quadrilateral we add one vertex, two edges and one face. Euler’s equation still works.

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 çoxbucaqlı üzlü üç ölçülü formalı polyhedra torlarına çox bənzəyir. Elastik lentlərdən düzəldilmiş polyhedra düşünsək, düz, planar qrafik halına gətirilənə qədər uzatdıqlarını xəyal edə bilərik:

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ı

Mathigon-a daxil olun

Paylaşın

Bizə rəy göndərin

Geribildiriminiz üçün təşəkkür edirik!

Parametrlər

Tercihləri göstərin

Tərəqqi sıfırlayın

Lüğət

Qrafiklər və ŞəbəkələrPlanar Qrafiklər

Planarallıq

Euler Formulu

Dili dəyişdirin