Apa itu Teori Graf, dan bagaimana graf didefinisikan seperti itu?

Pada tahun 1736, berdasarkan karya fisikawan-matematikawan Swiss Leonhard Euler (1707-1783), diamati bahwa suksesi simpul mendefinisikan sebuah jalur, namun, jika jalur tersebut terdiri dari simpul yang berbeda tanpa tepi yang berulang, itu disebut jalur atau jalur euler; jika tambahan kita tiba di titik awal, melintasi setiap tepi hanya sekali, maka kita memiliki siklus (sirkuit) Euler.

Kutipan (APA)

alexander barraza | Juli 2022
Gelar dalam fisika

Untuk bagiannya, kami mendefinisikan grafik sebagai pasangan terurut (PERGI) di mana v menunjuk himpunan (tidak kosong) dari semua simpul atau simpul dari suatu graf, sedangkan SEBUAH menunjuk himpunan (bisa kosong) dari semua sisi atau garis yang menghubungkan simpul-simpul dari suatu graf. Unsur-unsur himpunan SEBUAH dapat ditunjuk sebagai pasangan tak berurutan {v, w} di mana v dan w adalah elemen (simpul atau simpul) dari v, dengan cara ini kemudian dikatakan bahwa v dan w adalah simpul-simpul yang bertetangga (mereka dihubungkan oleh suatu sisi).

Teori graf muncul dari jawaban yang diberikan oleh Euler terhadap masalah kecerdikan populer yang bertanya-tanya bagaimana cara menyeberangi tujuh jembatan itu. bergabung dengan dua pulau komunitas Königsberg (bagian dari Jerman pada saat itu, dan saat ini Kaliningrad, di Rusia), di antara mereka dan dengan daratan tanpa menggunakan dua kali jembatan yang sama dan tiba di titik awal (terletak di daratan) apa pun itu, menentukan bahwa dalam hal ini, pada akhirnya, tidak ada bisa.

Masalah tujuh jembatan Königsberg

Euler memodelkan Königsberg sebagai grafik di mana setiap titik (simpul atau simpul) mewakili jembatan dan setiap garis (sisi) jalur di darat:

Apa solusi untuk masalah ini?

tidak ada satu pun larutan yang memenuhi kondisi yang dipaksakan, karena, seperti yang ditunjukkan Euler, simpul-simpulnya tidak berderajat genap, yaitu, jumlah garis yang genap tidak memengaruhi setiap titik _[3]. Sepertinya kita tidak bisa berbuat banyak dengan struktur yang didefinisikan sesederhana ini, namun, seperti yang sering terjadi di matematika, Terkadang hal-hal tidak seperti yang terlihat. Dengan demikian, salah satu bidang yang paling produktif, transversal dan interdisipliner _[4] pengetahuan manusia, teori graf.

Grafik Euler atau dengan lintasan Euler?

Graf-graf berikut semuanya memiliki lintasan Euler: _[5]. Apakah mereka semua memiliki siklus Euler?

Mari kita ambil grafik ketiga:

Mari kita beri nomor pada simpul:

Kemudian kita lihat bahwa lintasan yang ditentukan oleh barisan {3,4,6,2,1,3,7,6,5,4,2} adalah lintasan Euler, karena ia melewati seluruh grafik tanpa tepi berulang, tetapi itu bukan siklus Euler, karena tidak mencapai titik awal. Apa yang akan terjadi jika kita memberi nomor pada simpul secara berbeda? Tidak banyak, kecuali bahwa sekarang jalurnya akan ditentukan oleh suksesi yang berbeda. Apa yang akan terjadi jika kita mengikuti jalan yang berbeda dari yang diusulkan dalam solusi awal kita? Pertanyaan ini sedikit lebih rumit untuk dijawab, dan ini melibatkan algoritme yang biasanya disukai oleh para insinyur perangkat lunak. pemrograman.

Untuk bukti yang lebih ketat dari apa yang dipaparkan di sini, kita harus mengacu pada hasil berikut:

"Menjadi G grafik terhubung _[6]. Lalu ya G memiliki sirkuit Euler, derajat setiap simpulnya genap, sedangkan jika G memiliki jalur Euler, G memiliki tepat dua simpul berderajat ganjil _[7] (tepatnya simpul di mana jalur dimulai dan berakhir)".

Kami kemudian dapat memverifikasi bahwa, pada kenyataannya, dalam grafik yang kami ambil, hanya simpul 3 dan 6 yang memiliki derajat ganjil (ini akan terjadi bahkan jika penomoran simpul berbeda), oleh karena itu graf tersebut memiliki jalur eulerian _[8]. Untuk grafik yang tersisa, kita dapat melanjutkan dengan cara yang analog dan memverifikasi apakah memang mereka memiliki jalur dan Siklus Euler, atau dengan kata lain, dapatkah kita menggambar grafik seperti itu tanpa mengambil pensil dan mengulanginya? garis? Jawaban atas pertanyaan ini dapat disimpulkan dari apa yang telah dijelaskan sejauh ini, tetapi ini merupakan latihan menarik dalam hal keterampilan motorik halus, kecerdikan dan kesabaran, saya mengajak pembaca untuk menemukan dan menggambar grafik 6 atau lebih simpul dengan lintasan Euler.

Apakah ada jenis grafik lain? Apakah teori graf memiliki aplikasi di dunia 'nyata'?

Graf yang telah kita ulas secara singkat ini, hanyalah salah satu dari sekian banyak jenis graf yang kita temukan dalam teori graf. Kita juga dapat menemukan graf seperti pohon, yang sangat representatif dalam himpunan di mana elemen-elemennya dapat diklasifikasikan dalam hierarki dan dalam penghitungan penghitungan dan kemungkinan_[9], digraf, graf Hamilton _[10], dll.

Gambar Model Grafis dan Jaringan di Psycho., oleh Ruiz, Ana María.

Teka-teki ini, jika kita ingin menyebutnya demikian, memiliki penerapan yang sangat besar di dunia saat ini, dalam situasi yang beragam seperti: biologi molekuler _[11], komputasi_[12], telekomunikasi _[13] dan analisis jaringan _[14]. Patut ditanyakan kemudian: Bukankah setidaknya aneh bahwa masalah hampir dangkal akan menjadi salah satu hasil matematika yang paling menarik dan mencolok? Mungkin, untuk ini, kontribusi dari salah satu pemikir umat manusia yang paling terkenal diperlukan.