Grafik padanan

Grafik padanan

Ksenia Pakhomova
"Quantic" №8, 2015

Dalam "Quantica" nombor 10 untuk 2014, kami bercakap tentang pereka kacang. Kami berharap bahawa anda, pembaca yang sayang, telah membina banyak polyhedrons, istana, jambatan dan lain-lain perkara yang indah.

Tetapi adakah anda tahu bahawa dengan bantuan kacang dan tisu gigi graf yang indah dan terbuka dibina di atas kapal terbang, dan masalah teori graf sendiri dipelajari lebih seronok? Perkataan "graf" dalam matematik bermaksud gambar di mana beberapa titik ditarik, yang mana sebahagiannya dihubungkan oleh segmen atau busur. Titik dipanggil simpul graf, dan segmen (arka) adalah pinggirnya. Dalam kes kita, puncaknya adalah kacang, tepi lurus adalah tusuk gigi. Dalam pembinaan, struktur elegan dan tahan lama diperolehi.

Kaedah teori grafik telah mendapat pengiktirafan bukan sahaja dari ahli matematik, tetapi juga dari para jurutera, ahli ekonomi, ahli psikologi, ahli bahasa, ahli biologi, dan ahli kimia. Yang terakhir sering dengan bantuan graf menggambarkan molekul pelbagai bahan. Cuba untuk membina sendiri, sebagai contoh, molekul air, butana dan sikloheksana:

Pernahkah anda perhatikan bahawa semua tepi tiga graf molekul ini mempunyai panjang yang sama dan tidak bersilang? Grafik sedemikian dalam matematik dipanggil matchboxes.Mereka mendapat nama mereka, kerana mereka mudah diletakkan di pesawat dengan bantuan pertandingan.

Mudah untuk membina grafik perlawanan. Pada akhir abad yang lalu, sejumlah besar hasil matematik pada grafik perlawanan muncul, yang sebahagian besarnya berkaitan dengan ciri-ciri seperti bilangan simpang, set darjah, dan yang lain.

Ijazah simpang dipanggil bilangan tepi yang muncul dari situ. Jika semua darjah graf adalah sama, maka dipanggil biasa. Berikut adalah graf pertandingan biasa darjah 0, 1, 2 dan 3.

Pada tahun 1986, Heiko Harbort menemui pertandingan perlawanan biasa, yang dinamakan selepas Harbour Earl. Ia mempunyai 104 tepi dan 52 titik, yang darjahnya sama dengan empat.

Tugas matematik yang menarik adalah untuk mencari graf pertandingan terkecil, iaitu graf yang mempunyai bilangan paling sedikit simpul dan mempunyai set darjah yang diberikan terlebih dahulu. Daripada graf biasa di atas mengenai empat yang pertama, ia terbukti bahawa mereka adalah yang terkecil. Grafik pertandingan biasa gelaran 5 dan ke atas tidak wujud.

Pertimbangkan graf pertandingan yang mempunyai simpang mempunyai dua nilai darjah {m, n}. Graf padanan terkecil dengan darjah {0, n} adalah kesatuan satu titik dan grafik gelaran terkecil n. Graf padanan terkecil dengan darjah {1, n} ialah graf bintang dengan n + 1 simpul.

Jadual di bawah menunjukkan graf pertandingan yang paling kecil dengan darjah {m, n}:

Minimaliti graf dari baris pertama dibuktikan. Cuba teruskan baris ini – bina untuk setiap satu n = 9, 10, 11, … graf dengan kuasa {2, n}.

Lihat betapa indahnya grafik padanan yang paling kecil dengan darjah {4, 5}, {4, 6}, {4, 8}:

Dengan cara ini, cuba cepat mencari bahagian atas ijazah 5 pada grafik pertama ini.

Gavin Theobald mendapati grafik perlawanan paling kurang diketahui dengan darjah {4, 7}:

Berikut ialah contoh grafik padanan yang paling kecil dengan darjah {4, 9}, {4, 10}, {4, 11}:

Grafik perlawanan dengan darjah {4, 12} belum dijumpai. Ia mungkin n ≥ 12 grafik perlawanan dengan darjah {4, ntidak. Tetapi graf dengan darjah {m, n} di mana m dan n lebih daripada 5, pasti tidak wujud.

Terdapat masalah lain dengan graf pertandingan, kedua-dua pesawat dan ruang angkasa.1. Dan banyak soalan tetap terbuka. Adalah luar biasa bahawa pengajaran yang mudah, seperti pembinaan kacang polong, membolehkan anda menyentuh masalah-masalah yang serius yang berkaitan dengan ahli matematik moden.

Akhirnya, kami mempersembahkan beberapa graf pertandingan yang tidak minimum, tetapi sangat cantik.


1 Maklumat lanjut tentang tugas lain pada grafik perlawanan boleh didapati di laman web. Sihir matematik.

Artis Elena Tsvetaeva


Like this post? Please share to your friends:
Tinggalkan Balasan

;-) :| :x :twisted: :smile: :shock: :sad: :roll: :razz: :oops: :o :mrgreen: :lol: :idea: :grin: :evil: :cry: :cool: :arrow: :???: :?: :!: