Teori grafik- salah satu bagian matematika diskrit yang paling luas, banyak digunakan dalam memecahkan masalah ekonomi dan manajemen, dalam pemrograman, kimia, desain dan studi rangkaian listrik, komunikasi, psikologi, psikologi, sosiologi, linguistik, dan bidang pengetahuan lainnya. Teori grafik mempelajari secara sistematis dan konsisten sifat-sifat graf, yang dapat dikatakan terdiri dari himpunan titik-titik dan himpunan garis yang mewakili hubungan antar titik-titik tersebut. Pendiri teori graf dianggap Leonhard Euler (1707-1882), yang memecahkan masalah jembatan Königsberg yang terkenal pada tahun 1736.

Grafik dibangun untuk menampilkan relasi pada himpunan. Misalkan saja suatu himpunan A = {A1 , A 2 , ... A N)- banyak orang, dan setiap elemen akan ditampilkan sebagai titik. Sekelompok B = {B1 , B 2 , ... B M)- banyak koneksi (garis lurus, busur, segmen - belum masalah). Di lokasi syuting A hubungan kenalan antara orang-orang dari kumpulan ini diberikan. Membangun grafik dari titik dan penghubung. Tautan akan menghubungkan pasangan orang yang saling mengenal. Secara alami, jumlah kenalan beberapa orang mungkin berbeda dari jumlah kenalan orang lain, dan beberapa mungkin tidak mengenal siapa pun (elemen tersebut akan menjadi titik-titik yang tidak terhubung satu sama lain). Jadi kita punya grafiknya!

Apa yang pertama kita sebut “titik” seharusnya disebut simpul dari grafik, dan apa yang kita sebut “koneksi” seharusnya disebut sisi dari grafik.

Teori graf tidak memperhitungkan sifat spesifik himpunan A Dan B. Ada sejumlah besar masalah spesifik yang sangat berbeda, ketika menyelesaikannya, seseorang dapat melupakan untuk sementara waktu tentang konten spesifik dari himpunan dan elemen-elemennya. Kekhususan ini sama sekali tidak mempengaruhi kemajuan pemecahan masalah, betapapun sulitnya! Misalnya, ketika memutuskan apakah hal itu mungkin dari suatu titik A langsung ke intinya e, hanya bergerak sepanjang garis yang menghubungkan titik-titik, tidak peduli apakah kita berhadapan dengan orang, kota, angka, dll. Namun, ketika masalahnya terpecahkan, kami mendapatkan solusi yang benar untuk konten apa pun yang dimodelkan sebagai grafik. Oleh karena itu, tidak mengherankan bahwa teori grafik adalah salah satu alat paling populer dalam penciptaan kecerdasan buatan: bagaimanapun juga, kecerdasan buatan dapat berdiskusi dengan lawan bicara tentang masalah cinta, masalah musik atau olahraga, dan masalah penyelesaian berbagai masalah. , dan melakukan ini tanpa transisi apa pun (peralihan), yang tanpanya seseorang tidak dapat melakukannya dalam kasus seperti itu.

Dan sekarang definisi matematika yang ketat dari sebuah grafik.

Definisi 1.Ini disebut grafik suatu sistem objek-objek yang bersifat sembarang (simpul) dan tautan (tepi) yang menghubungkan beberapa pasang objek-objek tersebut.

Definisi 2. Membiarkan V– himpunan simpul, elemen (tidak kosong). ay∈V- puncak. Grafik G = G(V) dengan banyak simpul V ada keluarga berpasangan tertentu yang bentuknya: e = (A, B) , Di mana A,B∈V , menunjukkan simpul mana yang tetap terhubung. Setiap pasang e = (A, B) - tepi grafik. Sekelompok kamu- banyak tepinya e grafik. Puncak A Dan B– titik akhir dari tepi e .

Grafik sebagai struktur data. Meluasnya penggunaan teori graf dalam ilmu komputer dan teknologi informasi disebabkan oleh penambahan konsep graf sebagai struktur data pada definisi di atas. Dalam ilmu komputer dan teknologi informasi, grafik didefinisikan sebagai struktur data nonlinier. Lalu apa yang dimaksud dengan struktur data linier dan apa perbedaan grafiknya? Struktur data linier dicirikan oleh fakta bahwa mereka menghubungkan elemen melalui hubungan tipe “lingkungan sederhana”. Struktur data linier misalnya array, tabel, daftar, antrian, tumpukan, string. Sebaliknya, struktur data nonlinier adalah struktur di mana elemen-elemennya ditempatkan pada tingkat hierarki yang berbeda dan dibagi menjadi tiga jenis: asli, dihasilkan, dan serupa. Jadi, grafik adalah struktur data nonlinier.

Kata grafik berasal dari bahasa Yunani, dari kata “Saya menulis”, “Saya menjelaskan”. Dari awal artikel ini kita mengetahui apa sebenarnya yang digambarkan oleh grafik: grafik tersebut menggambarkan hubungan. Artinya, grafik apa pun menggambarkan hubungan. Dan sebaliknya: hubungan apa pun dapat digambarkan sebagai grafik.

Konsep dasar teori graf

Konsep kejadian juga diperlukan ketika mengembangkan algoritma untuk memecahkan banyak masalah praktis dengan grafik. Misalnya, Anda dapat membiasakan diri dengan implementasi perangkat lunak traversal kedalaman-pertama dari grafik yang diwakili oleh matriks kejadian. Idenya sederhana: Anda hanya dapat bergerak melalui simpul-simpul yang dihubungkan oleh sisi-sisinya. Dan jika beberapa nilai diberikan ke tepinya ("skala", paling sering dalam bentuk angka, grafik seperti itu disebut berbobot atau diberi label), maka masalah terapan yang kompleks dapat diselesaikan, beberapa di antaranya disebutkan di paragraf terakhir dari pelajaran ini.

Masalah klasik teori graf dan solusinya

Salah satu contoh karya teori graf dan penerapan graf yang pertama kali diterbitkan adalah karya “Masalah Jembatan Königsberg” (1736), yang ditulis oleh ahli matematika terkemuka abad ke-18 Leonhard Euler. Masalahnya berisi sungai, pulau-pulau yang tersapu oleh sungai ini, dan beberapa jembatan. Pertanyaan masalahnya: apakah mungkin, setelah meninggalkan suatu titik tertentu, melintasi setiap jembatan hanya satu kali dan kembali ke titik awal? (gambar di bawah)

Permasalahannya dapat dimodelkan sebagai berikut: satu titik dihubungkan pada setiap bidang tanah, dan dua titik dihubungkan oleh sebuah garis jika dan hanya jika bidang-bidang tanah yang bersangkutan dihubungkan oleh sebuah jembatan (gambar di bawah, garis-garis penghubung digambarkan dalam garis putus-putus) . Dengan demikian, grafik dibuat.

Jawaban Euler terhadap pertanyaan masalah adalah sebagai berikut. Jika soal ini memiliki solusi positif, maka pada grafik yang dihasilkan akan terdapat jalur tertutup yang melewati setiap sisi dan hanya memuat setiap sisi satu kali. Jika jalur seperti itu ada, maka setiap titik harus mempunyai jumlah sisi yang genap. Namun graf yang dihasilkan memiliki simpul yang jumlah sisinya ganjil. Oleh karena itu, permasalahan tersebut tidak mempunyai solusi yang positif.

Menurut tradisi yang ada, graf Euler adalah graf yang memungkinkan untuk melintasi semua simpul dan pada saat yang sama hanya melintasi satu sisi hanya sekali. Di dalamnya, setiap simpul hanya boleh mempunyai jumlah rusuk yang genap. Soal tingkat kesulitan sedang pada graf Euler terdapat pada materi “Tipe-tipe dasar graf”.

Pada tahun 1847, Kirchhoff mengembangkan teori pohon untuk menyelesaikan sistem persamaan aljabar linier secara simultan, yang memungkinkan seseorang menemukan nilai arus di setiap konduktor (busur) dan di setiap rangkaian rangkaian listrik. Mengabstraksi dari rangkaian listrik dan rangkaian yang mengandung hambatan, kapasitor, induktansi, dll., ia mempertimbangkan struktur kombinatorial bersesuaian yang hanya berisi simpul dan sambungan (tepi atau busur), dan untuk sambungan tidak perlu memperhitungkan jenis elemen listrik apa. mereka berkorespondensi dengan . Jadi, Kirchhoff mengganti setiap rangkaian listrik dengan grafik yang sesuai dan menunjukkan bahwa untuk menyelesaikan sistem persamaan, tidak perlu mempertimbangkan setiap siklus dari grafik rangkaian listrik secara terpisah.

Cayley pada tahun 1858, ketika mengerjakan masalah praktis dalam kimia organik, menemukan kelas grafik penting yang disebut pohon. Dia berusaha membuat daftar isomer hidrokarbon jenuh, dengan jumlah atom karbon tertentu. Cayley pertama kali merumuskan masalahnya secara abstrak: temukan jumlah semua pohon P simpul yang masing-masing mempunyai simpul dengan derajat 1 dan 4. Ia tidak dapat segera menyelesaikan masalah ini, dan ia mulai mengubah rumusannya sedemikian rupa sehingga masalah pencacahan baru dapat diselesaikan:

pohon berakar (yang salah satu simpulnya dipilih);
semua pohon;
pohon yang derajat puncaknya tidak melebihi 4;
pohon yang derajat simpulnya 1 dan 4 (pernyataan soal kimia).

Buat grafik masalah untuk memperkuat konsep dasar

Contoh 1. Membiarkan A- kumpulan angka 1, 2, 3: A= (1, 2, 3) . Buatlah grafik untuk menampilkan hubungan "

Larutan. Jelasnya, angka 1, 2, 3 harus direpresentasikan sebagai simpul-simpul suatu graf. Kemudian setiap pasang simpul harus dihubungkan oleh satu sisi. Memecahkan masalah ini, kami sampai pada konsep dasar teori graf seperti grafik berarah dan tidak berarah. Graf tak berarah adalah graf yang sisi-sisinya tidak mempunyai arah. Atau, seperti yang lebih sering dikatakan, urutan kedua ujung suatu sisi tidaklah signifikan. Faktanya, grafik yang dibuat di awal pelajaran ini dan mencerminkan hubungan kenalan antar orang tidak memerlukan arah tepi, karena dapat dikatakan bahwa "orang nomor 1" juga akrab dengan "orang nomor 2". sebagai "orang nomor 2" dengan "orang nomor 1". Dalam contoh kita saat ini, satu angka lebih kecil dari angka lainnya, namun tidak sebaliknya. Oleh karena itu, sisi-sisi grafik yang bersesuaian harus mempunyai arah yang menunjukkan bilangan mana yang lebih kecil dari bilangan lainnya. Artinya, urutan ujung tepinya penting. Graf seperti itu (yang sisi-sisinya mempunyai arah) disebut graf berarah atau digraf.

Jadi, dalam jumlah banyak A angka 1 lebih kecil dari angka 2 dan angka 3, dan angka 2 lebih kecil dari angka 3. Fakta ini kita tampilkan dengan sisi-sisi yang memiliki arah, yang ditunjukkan dengan panah. Kami mendapatkan grafik berikut:

Contoh 2. Membiarkan A- kumpulan angka 2, 4, 6, 14 : A= (2, 4, 6, 14) . Buat grafik untuk menampilkan relasi “habis dibagi” pada himpunan ini.

Larutan. Dalam contoh ini, beberapa sisi akan memiliki arah, dan beberapa tidak, yaitu, kita sedang membangun grafik campuran. Mari kita daftar relasi pada himpunan: 4 habis dibagi 2, 6 habis dibagi 2, 14 habis dibagi 2, dan setiap bilangan dari himpunan ini habis dibagi sendiri. Relasi ini, yaitu suatu bilangan yang habis dibagi dengan dirinya sendiri, akan ditampilkan dalam bentuk sisi-sisi yang menghubungkan titik dengan dirinya sendiri. Tepi seperti itu disebut loop. Dalam hal ini tidak perlu memberikan arahan pada loop. Jadi dalam contoh kita ada tiga tepi berarah beraturan dan empat loop. Kami mendapatkan grafik berikut:

Contoh 3. Biarkan diberikan set A= (α, β, γ) dan B= (a, b, c) . Buatlah grafik untuk menampilkan hubungan “hasil kali kartesius himpunan”.

Larutan. Seperti diketahui dari definisinya Produk Cartesius dari himpunan, tidak ada himpunan elemen terurut dari himpunan yang sama. Artinya, dalam contoh kita, Anda tidak dapat menggabungkan huruf Yunani dengan huruf Yunani dan Latin dengan Latin. Fakta ini ditampilkan sebagai grafik bipartit, yaitu simpul yang simpul-simpulnya dibagi menjadi dua bagian sehingga simpul-simpul yang termasuk dalam bagian yang sama tidak saling berhubungan. Kami mendapatkan grafik berikut:

Contoh 4. Agen real estate mempekerjakan manajer Igor, Sergey dan Peter. Objek O1, O2, O3, O4, O5, O6, O7, O8 dilayani. Buatlah grafik untuk menampilkan hubungan “Igor bekerja dengan objek O4, O7”, “Sergey bekerja dengan objek O1, O2, O3, O5, O6”, “Peter bekerja dengan objek O8”.

Larutan. Grafik yang menampilkan hubungan ini juga akan bersifat bipartit, karena pengelola tidak bekerja dengan pengelola dan objek tidak bekerja dengan objek. Namun berbeda dengan contoh sebelumnya, grafiknya akan berarah. Faktanya, misalnya Igor bekerja dengan objek O4, tetapi objek O4 tidak bekerja dengan Igor. Seringkali, ketika sifat relasi seperti itu terlihat jelas, kebutuhan untuk memberikan arah ke tepinya mungkin tampak seperti “kebodohan matematis”. Tapi tetap saja, ini mengikuti sifat matematika yang ketat, jika hubungannya hanya sepihak, maka perlu diberi arah ke tepinya. Dalam aplikasi relasional, ketelitian ini membuahkan hasil, misalnya, dalam program yang dirancang untuk perencanaan, yang juga menggunakan grafik dan rute sepanjang simpul dan tepi harus melewati arah tertentu secara ketat. Jadi, kita mendapatkan grafik bipartit berarah berikut:

Dan lagi ke contoh dengan angka.

Contoh 5. Biarkan satu set diberikan C = {2, 3, 5, 6, 15, 18} . Buatlah grafik yang mengimplementasikan relasi yang mendefinisikan semua pasangan bilangan A Dan B dari banyak C, di mana, ketika membagi elemen kedua dengan elemen pertama, kita memperoleh hasil bagi yang bilangan bulatnya lebih besar dari 1.

Larutan. Grafik yang menampilkan hubungan-hubungan ini akan berorientasi, karena kondisinya memuat penyebutan elemen kedua dan pertama, yaitu tepinya akan diarahkan dari elemen pertama ke elemen kedua. Dari sini jelaslah unsur mana yang pertama dan mana yang kedua. Mari kita tambahkan juga beberapa terminologi: tepi yang berorientasi biasanya disebut busur. Akan ada 7 busur di grafik kita: e1 = (3, 15) , e2 = (3, 18) , e3 = (5, 15) , e4 = (3, 6) , e5 = (2, 18) , e6 = (6, 18) , e7 = (2, 6) . Dalam contoh ini, sisi-sisi (busur) dari grafik hanya diberi nomor, tetapi nomor seri bukanlah satu-satunya hal yang dapat ditetapkan pada suatu busur. Busur juga dapat dikaitkan dengan skala yang berarti, misalnya, biaya pengiriman barang dari satu titik ke titik lain. Namun kita akan mengenal bobot busur nanti dan lebih detail. Jadi, kita mendapatkan grafik berarah berikut:

Seperti yang telah kita ketahui dari bagian pengantar teori, teori graf tidak memperhitungkan sifat spesifik himpunan dan dengan bantuan graf yang sama dimungkinkan untuk mendefinisikan relasi pada himpunan dengan isi yang sangat berbeda. Artinya, konten ini dapat diabstraksi dari saat memodelkan suatu tugas. Mari beralih ke contoh yang mengilustrasikan sifat luar biasa dari teori graf.

Contoh 6. Pada selembar papan catur berukuran 3 X 3 ditempatkan dua buah ksatria putih dan dua ksatria hitam seperti pada gambar di bawah ini.

Apakah mungkin untuk memindahkan ksatria ke keadaan yang ditunjukkan pada gambar berikut, dengan tidak lupa bahwa dua buah bidak tidak boleh berada di kotak yang sama?

Larutan. Pada graf yang dikonstruksi, pasangan simpul akan dihubungkan dengan relasi “gerakan ksatria”. Artinya, satu titik adalah titik tempat ksatria pergi, dan titik lainnya adalah titik tempat ia tiba, dan sel perantara dari huruf "r" akan berada di luar hubungan ini. Kami mendapatkan grafik berikut:

Namun desainnya ternyata rumit. Sel-sel papan catur terlihat di dalamnya, dan banyak tepi grafik berpotongan. Apakah mungkin untuk mengabstraksikan tampilan fisik papan catur dan membayangkan hubungannya dengan lebih sederhana? Ternyata hal itu mungkin saja terjadi. Pada graf baru, simpul-simpul yang bertetangga adalah simpul-simpul yang dihubungkan oleh hubungan “gerakan ksatria”, dan bukan simpul-simpul yang bertetangga di papan catur (gambar di bawah).

Sekarang mudah untuk melihat bahwa jawaban atas pertanyaan mengenai masalah ini adalah negatif. Pada keadaan awal tidak ada ksatria hitam di antara dua ksatria putih, namun pada keadaan akhir harus ada ksatria hitam ini. Tepi grafik ditempatkan sedemikian rupa sehingga dua ksatria yang berdekatan tidak dapat melompati satu sama lain.

Contoh 7. Soal tentang serigala, kambing dan kubis. Di salah satu tepian sungai terdapat manusia (H), perahu, serigala (V), kambing (Kz) dan kubis (Kp). Seseorang dan tidak lebih dari satu benda yang diangkut dapat berada di dalam perahu pada waktu yang bersamaan. Seseorang harus memindahkan semua benda ke sisi lain, dengan memperhatikan syarat: serigala tidak boleh ditinggalkan tanpa pengawasan dengan kambing dan kambing dengan kubis.

Larutan. Dalam graf yang dikonstruksi, simpul-simpulnya adalah konfigurasi, dan sisi-sisinya adalah hubungan “hubungan satu kali naik perahu” antar konfigurasi. Konfigurasi artinya susunan benda pada tepian asal dan pada tepian seberang. Setiap konfigurasi ditampilkan sebagai ( A|B) , Di mana A- benda yang terletak di pantai aslinya, dan B- benda yang terletak di tepi seberang. Oleh karena itu, konfigurasi awalnya adalah - (PMCpKz| ) . Misalnya setelah mengangkut kambing ke seberang, konfigurasinya akan seperti ini (VKp|ChKz) . Konfigurasi akhir selalu ( |PMCpKz) . Sekarang kita dapat membuat grafik, sudah mengetahui apa arti simpul dan sisi:

Mari kita letakkan simpul-simpul pada grafik sedemikian rupa sehingga sisi-sisinya tidak berpotongan, dan simpul-simpul yang bertetangga adalah simpul-simpul yang dihubungkan oleh suatu hubungan pada grafik. Maka akan lebih mudah untuk melihat hubungannya (untuk memperbesar gambar, klik kiri di atasnya):

Seperti yang bisa kita lihat, ada dua rute berkelanjutan yang berbeda dari konfigurasi awal hingga konfigurasi akhir. Oleh karena itu, masalah tersebut memiliki dua solusi berbeda (dan keduanya benar).

Teori grafik dan masalah terapan modern yang paling penting

Berdasarkan teori graf, metode telah dikembangkan untuk memecahkan masalah terapan di mana sistem yang sangat kompleks dimodelkan dalam bentuk grafik. Dalam model ini, node berisi komponen individual, dan edge mewakili hubungan antar komponen. Biasanya, grafik berbobot digunakan untuk memodelkan jaringan transportasi, sistem antrian, dan perencanaan jaringan. Kita telah membicarakannya; ini adalah grafik di mana bobot diberikan pada busur.

Grafik pohon digunakan, misalnya, untuk membuat pohon keputusan(berfungsi untuk analisis risiko, analisis kemungkinan keuntungan dan kerugian dalam kondisi ketidakpastian). Dengan menggunakan teori graf, dikembangkan dan berbagai model matematika lainnya untuk memecahkan masalah dalam bidang studi tertentu.

Grafik dan masalah aliran

Rumusan masalah. Terdapat sistem pipa air yang diwakili oleh grafik pada gambar di bawah ini.

Setiap busur pada grafik mewakili sebuah pipa. Angka-angka di atas busur (skala) adalah kapasitas pipa. Node adalah tempat di mana pipa-pipa dihubungkan. Air mengalir melalui pipa hanya dalam satu arah. Simpul S- sumber air, simpul T- saham. Hal ini diperlukan untuk memaksimalkan volume air yang mengalir dari sumber ke saluran pembuangan.

Untuk mengatasi masalah aliran dapat menggunakan metode Ford-Fulkerson. Ide metode: pencarian aliran maksimum dilakukan secara bertahap. Pada awal algoritma, aliran diatur ke nol. Pada setiap langkah berikutnya, nilai aliran meningkat, sehingga dicari jalur pelengkap yang melaluinya aliran tambahan tersebut akan tiba. Langkah-langkah ini diulangi selama ada jalur tambahan. Permasalahan tersebut telah berhasil diterapkan di berbagai sistem terdistribusi: sistem catu daya, jaringan komunikasi, sistem kereta api dan lain-lain.

Grafik dan perencanaan jaringan

Dalam masalah perencanaan proses kompleks yang terdiri dari banyak pekerjaan, beberapa di antaranya dilakukan secara paralel dan beberapa dilakukan secara berurutan, grafik berbobot, yang dikenal sebagai jaringan PERT, telah banyak digunakan.

PERT - Teknik Evaluasi dan Tinjauan Program (Proyek) - teknik untuk mengevaluasi dan menganalisis program (proyek), yang digunakan dalam manajemen proyek.

Jaringan PERT adalah grafik berarah asiklik berbobot di mana setiap busur mewakili suatu pekerjaan (tindakan, operasi), dan bobot busur adalah waktu yang diperlukan untuk menyelesaikannya.

Jika ada busur di jaringan ( A, B) Dan ( B, C) , maka usaha tersebut diwakili oleh busur ( A, B) harus diselesaikan sebelum pekerjaan yang diwakili oleh busur ( B, C) . Setiap simpul ( aySaya) mewakili titik waktu di mana semua pekerjaan, ditentukan oleh busur yang berakhir pada sebuah titik ( aySaya).

Di kolom seperti ini:

satu simpul, yang tidak memiliki pendahulu, menentukan waktu mulai pekerjaan;
satu simpul, yang tidak memiliki pengikut, berhubungan dengan momen ketika himpunan pekerjaan selesai.

Jalur dengan panjang maksimum antara simpul-simpul grafik tersebut (dari awal hingga akhir proses kerja) disebut jalur kritis. Untuk mengurangi waktu yang dibutuhkan untuk menyelesaikan seluruh kompleks pekerjaan, perlu dicari pekerjaan yang terletak pada jalur kritis dan mengurangi durasinya dengan, misalnya, menarik tambahan pemain, mekanisme, dan teknologi baru.

Seluruh blok "Teori Grafik"

Teori graf adalah cabang matematika diskrit yang mempelajari objek yang direpresentasikan sebagai elemen individu (simpul) dan hubungan di antara mereka (busur, tepi).

Teori graf bermula dari penyelesaian masalah jembatan Königsberg pada tahun 1736 oleh ahli matematika terkenal Leonard Euler(1707-1783: lahir di Swiss, tinggal dan bekerja di Rusia).

Masalah tentang jembatan Königsberg.

Ada tujuh jembatan di kota Königsberg di Prusia di Sungai Pregal. Mungkinkah menemukan rute jalan kaki yang melintasi setiap jembatan tepat satu kali dan dimulai serta diakhiri di tempat yang sama?

Graf yang mempunyai rute yang dimulai dan berakhir pada titik yang sama dan melewati semua sisi graf tersebut tepat satu kali disebutGrafik Euler.

Urutan simpul (mungkin berulang) yang dilalui rute yang diinginkan, seperti rute itu sendiri, disebutSiklus Euler .

Masalah tiga rumah dan tiga sumur.

Ada tiga rumah dan tiga sumur, entah bagaimana letaknya di pesawat. Gambarlah jalan setapak dari setiap rumah ke setiap sumur agar jalan tersebut tidak berpotongan. Masalah ini diselesaikan (terbukti tidak ada solusinya) oleh Kuratovsky (1896 - 1979) pada tahun 1930.

Masalah empat warna. Pembagian bidang menjadi beberapa bidang yang tidak berpotongan disebut dengan kartu. Daerah peta disebut berdekatan jika mempunyai batas yang sama. Tugasnya adalah mewarnai peta sedemikian rupa sehingga tidak ada dua area yang berdekatan dicat dengan warna yang sama. Sejak akhir abad ke-19, telah diketahui hipotesis bahwa empat warna sudah cukup untuk ini. Hipotesisnya belum terbukti.

Inti dari solusi yang dipublikasikan adalah untuk mencoba sejumlah besar namun terbatas (sekitar 2000) jenis contoh tandingan potensial terhadap teorema empat warna dan menunjukkan bahwa tidak ada satu kasus pun yang merupakan contoh tandingan. Pencarian ini diselesaikan oleh program dalam waktu sekitar seribu jam pengoperasian superkomputer.

Tidak mungkin untuk memeriksa solusi yang dihasilkan “secara manual” - ruang lingkup pencacahan berada di luar kemampuan manusia. Banyak ahli matematika mengajukan pertanyaan: dapatkah “bukti program” semacam itu dianggap sebagai bukti sah? Lagi pula, mungkin ada kesalahan dalam program...

Oleh karena itu, kami hanya dapat mengandalkan keterampilan pemrograman penulis dan percaya bahwa mereka melakukan segalanya dengan benar.

Definisi 7.1. Menghitung G= G(V, E) adalah kumpulan dua himpunan berhingga: V – disebut banyak simpul dan himpunan E dari pasangan elemen dari V, yaitu EÍV´V, dipanggil banyak tepi, jika pasangannya tidak berurutan, atau banyak busur, jika berpasangan dipesan.

Dalam kasus pertama, grafik G(V, E) ditelepon tidak berorientasi, di detik – berorientasi.

CONTOH. Graf yang mempunyai himpunan simpul V = (a,b,c) dan himpunan sisi E =((a, b), (b, c))

CONTOH. Graf dengan V = (a,b,c,d,e) dan E = ((a, b), (a, e), (b, e), (b, d), (b, c) , (c, d)),

Jika e=(v 1 ,v 2), еОЕ, maka dikatakan rusuknya adalah e menghubungkan simpul v 1 dan v 2.

Dua simpul v 1,v 2 disebut bersebelahan, jika ada sisi yang menghubungkannya. Dalam situasi ini, masing-masing simpul dipanggil kejadian tepi yang sesuai .

Dua tulang rusuk yang berbeda bersebelahan, jika keduanya mempunyai simpul yang sama. Dalam situasi ini, masing-masing sisi dipanggil insidentil simpul yang sesuai .

Jumlah simpul grafik G mari kita tunjukkan ay, dan jumlah sisinya adalah e:

Representasi geometris dari grafik tersebut adalah sebagai berikut:

1) titik puncak suatu grafik adalah suatu titik dalam ruang (pada bidang);

2) sisi grafik tidak berarah – segmen;

3) busur dari grafik berarah – segmen berarah.

Definisi 7.2. Jika pada sisi e=(v 1 ,v 2) v 1 =v 2 terjadi, maka sisi e disebut lingkaran. Jika suatu graf membolehkan perulangan, maka graf tersebut disebut grafik dengan loop atau pseudograf .

Jika suatu graf membolehkan lebih dari satu sisi di antara dua simpul, maka graf tersebut disebut multigraf .

Jika setiap titik pada suatu graf dan/atau sisi diberi label, maka graf tersebut disebut ditandai (atau sarat ). Huruf atau bilangan bulat biasanya digunakan sebagai tanda.

Definisi 7.3. Grafik G (V , E ) ditelepon subgraf (atau bagian ) grafik G(V,E), Jika V V, E E. Jika V = V, Itu G ditelepon mencakup subgraf G.

Contoh 7 . 1 . Diberikan grafik tidak berarah.

Definisi 7.4. Grafiknya disebut menyelesaikan , Jika setiap kedua simpulnya dihubungkan oleh sebuah sisi. Lengkapi grafik dengan N simpul dilambangkan dengan K N .

Hitungan K 2 , KE 3, KE 4 dan K 5 .

Definisi 7.5. Grafik G=G(V, E) disebut dikotil , Jika V dapat direpresentasikan sebagai gabungan himpunan yang saling lepas, misalnya V=AB, jadi setiap sisinya mempunyai bentuk ( ay Saya , ay J), Di mana ay Saya A Dan ay J B.

Setiap sisi menghubungkan sebuah simpul dari A ke sebuah simpul dari B, tetapi tidak ada dua simpul dari A atau dua simpul dari B yang terhubung.

Graf bipartit disebut dikotil lengkap menghitung K M , N, Jika A mengandung M puncak, B mengandung N simpul dan untuk masing-masing ay Saya A, ay J B kita punya ( ay Saya , ay J)E.

Jadi, untuk semua orang ay Saya A, Dan ay J B ada tepi yang menghubungkan mereka.

K 12 K 23 K 22 K 33

Contoh 7 . 2 . Buatlah graf bipartit lengkap K 2.4 dan grafik lengkap K 4 .

Grafik satuanNkubus -dimensiDI DALAM N .

Titik-titik pada grafik adalah himpunan biner berdimensi-n. Tepi menghubungkan simpul-simpul yang berbeda dalam satu koordinat.

Contoh:

Teka-teki praktis berikut ini umum terjadi di kalangan penduduk Königsberg: apakah mungkin untuk menyeberangi semua jembatan di atas Sungai Pregolya tanpa melewati satupun dua kali? Pada tahun 1736, ahli matematika terkemuka Leonhard Euler menjadi tertarik pada masalah ini dan, dalam sebuah surat kepada seorang teman, memberikan bukti kuat bahwa hal tersebut tidak dapat dilakukan. Pada tahun yang sama, ia membuktikan rumus luar biasa yang menghubungkan jumlah simpul, permukaan, dan tepi polihedron dalam ruang tiga dimensi. Rumus ini secara misterius berlaku untuk grafik yang disebut “planar.” Kedua hasil ini meletakkan dasar bagi teori graf dan menggambarkan dengan baik arah perkembangannya hingga saat ini.

Tentang kursus

Mata kuliah ini berfungsi sebagai pengantar teori graf modern. Grafik sebagai objek matematika ternyata berguna dalam banyak permasalahan teoritis dan praktis. Intinya, mungkin, kompleksitas strukturnya sangat sesuai dengan kemampuan otak kita: ini adalah struktur visual dan terstruktur dengan jelas, namun, di sisi lain, cukup kaya untuk menangkap banyak fenomena non-sepele. Jika kita berbicara tentang aplikasi, tentu saja, jaringan besar langsung terlintas dalam pikiran: Internet, peta jalan, jangkauan seluler, dll. Mesin pencari seperti Yandex dan Google didasarkan pada algoritma grafik. Selain ilmu komputer, grafik secara aktif digunakan dalam bioinformatika, kimia, dan sosiologi. Dalam kursus kami, tentu saja, kami akan membahas masalah-masalah klasik, tetapi kami juga akan membahas hasil dan tren yang lebih baru, misalnya, tentang teori grafik ekstrem.

Format

Kursus ini terdiri dari 7 minggu pelatihan dan ujian. Agar berhasil menyelesaikan sebagian besar soal tes, cukup menguasai materi yang dibahas dalam perkuliahan. Seminar juga membahas permasalahan yang lebih kompleks yang mungkin menarik bagi pendengar yang sudah memahami dasar-dasar teori graf.

Sumber daya informasi

V. A. Emelichev, O. I. Melnikov, V. I. Sarvanov, R. I. Tyshkevich. Kuliah tentang teori graf. M.: Rumah Buku “Librokom”, 2009.
A. A. Zykov. Teori grafik terbatas. Novosibirsk: Nauka, 1969.
M. Swami, K. Thulasiraman. Grafik, jaringan dan algoritma. M.: Mir, 1984.
M. Aigner, G. M. Ziegler. Bukti Dari BUKU. Edisi keempat. Springer, 2009.
B. Bollobás. Teori Grafik Modern. Springer, 1998.
JA Bondy, USR Murty. Teori grafik. Springer, 2008.

Persyaratan

Materi disajikan dari dasar dan dalam bahasa yang mudah dipahami. Tujuan dari kursus ini tidak hanya untuk memperkenalkan Anda pada isu-isu dan metode teori graf, tetapi juga untuk mengembangkan budaya berpikir matematis di kalangan siswa yang belum siap. Oleh karena itu, kursus ini tersedia untuk banyak siswa. Untuk menguasai materi, pengetahuan matematika pada tingkat sekolah yang baik dan pengetahuan dasar kombinatorik sudah cukup.

Program kursus

Konsep graf dan jenis-jenis graf.
Berbagai penerapan grafik: dari jembatan Konigsberg hingga Internet.
Konektivitas graf, subgraf, dan derajat simpul.
Definisi pohon yang setara.
Planaritas dan kriteria Kuratowski
rumus Euler.
Bilangan kromatik dari graf planar.
Menghitung pohon: kode Prüfer dan rumus Cayley.
Rumus banyaknya grafik uniklik.
Siklus Euler dan kriteria Euler.
Siklus Hamilton. Kriteria Dirac dan kriteria Chvatal.
Pencocokan. Teorema Hall dan Koenig.
Teori grafik ekstrim. teorema Turan.
Analog dari teorema Turan untuk grafik pada bidang.
teori Ramsey. Berkencan di antara enam orang.
Penentuan bilangan Ramsey.
Batas bawah dan atas bilangan Ramsey.

Hasil belajar

Setelah berhasil menyelesaikan mata kuliah ini, mahasiswa akan mengenal konsep graf, jenis-jenis dan berbagai ciri serta sifat graf. Siswa akan belajar tentang masalah pewarnaan biasa dan kemungkinan menggambar grafik tertentu pada bidang tanpa memotong tepinya, dan juga akan belajar mengidentifikasi pohon dengan berbagai cara dan membuat daftarnya. Terakhir, pendengar akan mengenal konsep siklus Euler dan Hamilton, pencocokan, bahkan menyentuh permasalahan dalam teori graf ekstrem.

Mundur ke depan

Perhatian! Pratinjau slide hanya untuk tujuan informasi dan mungkin tidak mewakili semua fitur presentasi. Jika Anda tertarik dengan karya ini, silakan unduh versi lengkapnya.

Tujuan pelajaran:

memperkenalkan siswa pada konsep “Grafik”, prinsip dasar konstruksinya;

mengembangkan kemampuan untuk mengidentifikasi hubungan yang menghubungkan objek;

mengembangkan perhatian dan kemampuan penalaran logis;

mengembangkan gotong royong dan kemampuan bekerja dalam tim

konsolidasi pengetahuan yang diperoleh dalam praktik

pengembangan memori, perhatian;

pengembangan kemandirian;

pendidikan aktivitas kognitif.

Peralatan:

kelas komputer yang dilengkapi dengan teknologi modern, proyektor video, layar;
komputer dengan OS Windows XP, Microsoft Office 2003 PowerPoint;
perlengkapan papan (topik pelajaran, istilah baru). selebaran.

Rencana belajar.

II. Presentasi materi baru. (10 menit.)

AKU AKU AKU. Memperbaiki materi. Kerja praktek. (15-20 menit)

IV. Menyimpulkan pelajaran. (2 menit)

V.Pekerjaan Rumah.

I. Momen organisasi. Memperbarui pengetahuan.

Halo! Pelajaran kita disebut “Grafik”. Kita akan mengenal konsep “Grafik”, mempelajari cara menggambarkannya dan memecahkan masalah pada topik ini.

II Presentasi materi baru.

Karya pertama tentang teori graf adalah milik Leonhard Euler (1736), meskipun istilah “graf” pertama kali diperkenalkan pada tahun 1936 oleh matematikawan Hongaria Dénes König. Grafik adalah nama yang diberikan pada skema yang terdiri dari titik-titik dan ruas garis atau kurva yang menghubungkan titik-titik tersebut (contoh grafik ditunjukkan pada Gambar 1)

Dengan bantuan grafik, penyelesaian masalah yang dirumuskan dalam berbagai bidang pengetahuan sering kali disederhanakan: dalam otomasi, elektronik, fisika, kimia, dll. Dengan bantuan grafik, diagram jalan, pipa gas, jaringan panas dan listrik digambarkan. . Grafik membantu dalam memecahkan masalah matematika dan ekonomi.

Grafik – (dari bahasa Yunani grapho – saya menulis) adalah sarana untuk merepresentasikan secara visual unsur-unsur suatu benda dan hubungan di antara mereka. Ini adalah objek matematika yang luar biasa; dengan bantuannya Anda dapat memecahkan banyak masalah yang berbeda dan berbeda.

Grafik adalah semacam model informasi

Grafik terdiri dari simpul atau simpul yang dihubungkan oleh busur atau segmen – sisi. Suatu garis dapat berarah, yaitu mempunyai anak panah (busur); jika tidak berarah maka mempunyai tepi. Dua titik yang dihubungkan oleh suatu busur atau tepi disebut bertetangga.

Contoh grafik (Slide 4, 5, 6)

Tugas 1 (Slide 7):

Komunikasi luar angkasa telah terjalin antara sembilan planet di tata surya. Roket terjadwal terbang pada rute berikut:

Bumi - Merkurius; Pluto - Venus; Bumi - Pluto; Pluto - Merkurius; Merkurius - Venus; Uranus - Neptunus; Neptunus - Saturnus; Saturnus – Yupiter; Yupiter - Mars; Mars - Uranus.

Mungkinkah terbang dengan roket biasa dari Bumi ke Mars?

Solusi: Mari kita menggambar diagram kondisinya: kita akan menggambarkan planet sebagai titik, dan rute roket sebagai garis.

Sekarang jelas sekali bahwa tidak mungkin terbang dari Bumi ke Mars.

Dua titik yang dihubungkan oleh suatu busur atau tepi disebut bertetangga. Setiap sisi atau busur dikaitkan dengan sebuah angka. Angka tersebut dapat menunjukkan jarak antar pemukiman, waktu peralihan dari satu puncak ke puncak lainnya, dll.

Tugas 2 (9 slide) – solusi di papan tulis. Masha datang ke kebun binatang dan ingin melihat binatang sebanyak mungkin. Jalan mana yang harus dia ambil? Kuning, merah, hijau?

Tugas 3 (11 slide) – solusi di papan tulis. Lima tim sepak bola A, B, C, D, D harus bermain melawan satu sama lain. Sudah memainkan A dengan B, C, D; B dengan A, C, D. berapa pertandingan yang sudah dimainkan? Berapa banyak waktu yang tersisa untuk bermain?

Penyajian grafik (Slide 12)

Grafik dapat disajikan dalam bentuk daftar busur (AB; 7), secara grafis atau menggunakan tabel.

Daftar busur

Bentuk grafis

Bentuk tabel

(AB; 7),

	A	DI DALAM	DENGAN
A			3
DI DALAM			4
DENGAN	3	4

AKU AKU AKU. Materi penguat: Siswa diminta membagi menjadi beberapa kelompok dan menyelesaikan tugas. Bekerja dalam kelompok kecil, siswa mendiskusikan model berdasarkan pengetahuan teoritis yang diperoleh di awal pembelajaran. Hal ini memastikan pengulangan dan konsolidasi materi.

Tugas 2 (Slide 13)

IV. Ringkasan pelajaran

Teman-teman, kata-kata baru apa yang kamu pelajari hari ini? (Grafik, simpul grafik, tepi grafik.)

Apa yang dapat diwakilkan oleh simpul-simpul pada grafik tersebut? (Kota; objek yang; terhubung.)

Apa arti tepi grafik (jalur, pergerakan, arah)

Berikan contoh di mana dalam hidup kita bisa bertemu dengan mereka?

Bagaimana grafik digambarkan?

V.Pekerjaan Rumah. (Geser 15)

SEKOLAH MENENGAH LEMBAGA PENDIDIKAN OTONOM KOTA No.2

Siap

Legkokonets Vladislav, siswa kelas 10A

Penerapan praktis Teori Graf

Pengawas

L.I. Noskova, guru matematika

Seni. Bryukhovetskaya

2011

1.Pendahuluan..............................................................................................................................................3

2. Sejarah munculnya teori graf…………………………………………….………..4

3. Pengertian Dasar dan Teorema Teori Graf…………………………….………6

4. Soal diselesaikan dengan menggunakan grafik……………………………..………………………..8

4.1 Permasalahan yang terkenal…………………………….………………………...8

4.2 Beberapa permasalahan menarik…………………………….……………..9

5. Penerapan grafik dalam berbagai bidang kehidupan masyarakat……………………………...11

6. Penyelesaian masalah…………………………………………………………………………………...12

7. Kesimpulan………………….…………………………………………………………….13

8. Daftar referensi…….……………………………………………………………14

9.Lampiran……………………………………………………………………………….…………15

Perkenalan

Lahir dari pemecahan teka-teki dan permainan yang menghibur, teori grafik kini telah menjadi alat yang sederhana, mudah diakses, dan ampuh untuk memecahkan pertanyaan yang berkaitan dengan berbagai masalah. Grafik benar-benar ada di mana-mana. Dalam bentuk grafik, misalnya, Anda dapat menafsirkan peta jalan dan rangkaian listrik, peta geografis dan molekul senyawa kimia, hubungan antara manusia dan sekelompok orang. Selama empat dekade terakhir, teori graf telah menjadi salah satu cabang matematika yang berkembang paling pesat. Hal ini didorong oleh tuntutan bidang aplikasi yang berkembang pesat. Ini digunakan dalam desain sirkuit terpadu dan sirkuit kontrol, dalam studi automata, sirkuit logis, diagram blok program, di bidang ekonomi dan statistik, kimia dan biologi, dalam teori penjadwalan. Itu sebabnya relevansi Topiknya ditentukan, di satu sisi, oleh popularitas grafik dan metode penelitian terkait, dan di sisi lain, oleh sistem implementasinya yang holistik dan belum berkembang.

Menyelesaikan banyak permasalahan dalam hidup membutuhkan perhitungan yang panjang, bahkan terkadang perhitungan tersebut pun tidak membawa kesuksesan. Ini adalah apa permasalahan penelitian. Timbul pertanyaan: apakah mungkin menemukan solusi yang sederhana, rasional, singkat dan elegan untuk menyelesaikannya. Apakah penyelesaian masalah lebih mudah jika menggunakan grafik? Ini ditentukan topik penelitian saya: “Penerapan praktis teori graf”

Tujuan Penelitiannya adalah menggunakan grafik untuk mempelajari cara cepat menyelesaikan masalah praktis.

Hipotesis penelitian. Metode grafik sangat penting dan banyak digunakan dalam berbagai bidang ilmu pengetahuan dan aktivitas manusia.

Tujuan penelitian:

1. Pelajari literatur dan sumber internet tentang masalah ini.

2. Periksa keefektifan metode grafik dalam menyelesaikan masalah praktis.

3. Menarik kesimpulan.

Signifikansi praktis dari penelitian ini adalah hasilnya niscaya akan menggugah minat banyak orang. Belum adakah di antara Anda yang mencoba membangun silsilah keluarga Anda? Bagaimana cara melakukan ini dengan benar? Pimpinan suatu perusahaan angkutan mungkin harus memecahkan masalah penggunaan angkutan yang lebih menguntungkan ketika mengangkut barang dari suatu tujuan ke beberapa pemukiman. Setiap anak sekolah pernah menghadapi masalah transfusi yang logis. Ternyata masalah tersebut dapat diselesaikan dengan mudah menggunakan grafik.

Metode berikut digunakan dalam pekerjaan: observasi, pencarian, seleksi, analisis.

Sejarah teori graf

Pendiri teori graf dianggap sebagai ahli matematika Leonhard Euler (1707-1783). Sejarah teori ini dapat ditelusuri melalui korespondensi ilmuwan besar tersebut. Berikut terjemahan teks Latin, yang diambil dari surat Euler kepada ahli matematika dan insinyur Italia Marinoni, yang dikirim dari St. Petersburg pada 13 Maret 1736.

“Saya pernah diberi masalah tentang sebuah pulau yang terletak di kota Königsberg dan dikelilingi oleh sungai dengan tujuh jembatan yang melintasinya.

[Lampiran Gambar.1] Pertanyaannya adalah apakah seseorang dapat mengitarinya terus menerus, hanya melewati satu kali melewati setiap jembatan. Dan kemudian saya diberitahu bahwa belum ada seorang pun yang mampu melakukan ini, tetapi tidak ada yang membuktikan bahwa hal itu tidak mungkin. Pertanyaan ini, meskipun sepele, bagi saya tampaknya patut mendapat perhatian karena baik geometri, aljabar, maupun seni kombinatorial tidak cukup untuk menyelesaikannya. Setelah berpikir panjang, saya menemukan aturan yang mudah, berdasarkan bukti yang sepenuhnya meyakinkan, dengan bantuan yang memungkinkan dalam semua masalah semacam ini untuk segera menentukan apakah jalan memutar seperti itu dapat dilakukan melalui sejumlah dan sejumlah jembatan yang berlokasi. atau tidak. Letak jembatan Koenigsberg sedemikian rupa sehingga dapat direpresentasikan pada gambar berikut [Lampiran Gambar.2], di mana A menunjukkan sebuah pulau, dan B, C dan D - bagian benua yang dipisahkan satu sama lain oleh cabang sungai

Mengenai metode yang ia temukan untuk memecahkan masalah semacam ini, Euler menulis:

“Solusi ini, pada dasarnya, tampaknya tidak ada hubungannya dengan matematika, dan saya tidak mengerti mengapa seseorang harus mengharapkan solusi ini dari seorang ahli matematika daripada dari orang lain, karena keputusan ini didukung oleh penalaran saja, dan tidak ada perlu terlibat untuk menemukan solusi ini, ada hukum yang melekat dalam matematika. Jadi, saya tidak tahu bagaimana pertanyaan-pertanyaan yang tidak ada hubungannya dengan matematika lebih mungkin diselesaikan oleh ahli matematika daripada yang lain.”

Jadi apakah mungkin untuk melewati jembatan Königsberg hanya dengan melewati satu kali saja melewati masing-masing jembatan tersebut? Untuk mengetahui jawabannya, mari kita lanjutkan surat Euler kepada Marinoni:

“Pertanyaannya adalah untuk menentukan apakah mungkin untuk melewati ketujuh jembatan ini, melewati masing-masing jembatan hanya sekali, atau tidak. Aturan saya mengarah pada solusi berikut untuk pertanyaan ini. Pertama-tama, Anda perlu melihat berapa banyak area yang ada di sana. adalah, dipisahkan oleh air - seperti , yang tidak memiliki transisi lain dari satu ke yang lain, kecuali melalui jembatan, ada empat bagian seperti itu - A, B, C, D. Selanjutnya, Anda perlu membedakan apakah nomornya jumlah jembatan yang menuju ke masing-masing bagian ini adalah genap atau ganjil. Jadi, dalam kasus kita, lima jembatan mengarah ke bagian A, dan tiga jembatan masing-masing mengarah ke bagian lainnya, yaitu. Jumlah jembatan yang menuju ke masing-masing bagian adalah ganjil, dan ini saja yang ganjil. cukup untuk memecahkan masalah tersebut. Jika hal ini ditentukan, kita menerapkan aturan berikut: jika jumlah jembatan yang menuju ke masing-masing bagian adalah genap, maka jalan memutar yang dimaksud akan dimungkinkan, dan pada saat yang sama akan dimungkinkan untuk menyelesaikan masalah tersebut. mulailah jalan memutar ini dari bagian mana pun. Jika dua dari angka-angka ini ganjil, karena hanya satu yang tidak boleh ganjil, maka transisi genap dapat diselesaikan, seperti yang ditentukan, tetapi hanya permulaan jalan memutar yang harus diambil dari bagian mana pun. salah satu dari dua bagian yang jumlah jembatannya ganjil. Jika, pada akhirnya, terdapat lebih dari dua bagian yang jumlah jembatannya ganjil, maka pergerakan seperti itu umumnya tidak mungkin dilakukan... jika masalah lain yang lebih serius dapat ditimbulkan di sini, metode ini dapat memberikan manfaat yang lebih besar dan seharusnya jangan diabaikan." .

Definisi dasar dan teorema teori graf

Teori graf merupakan disiplin matematika yang diciptakan oleh upaya para ahli matematika, oleh karena itu penyajiannya mencakup definisi ketat yang diperlukan. Jadi, mari kita lanjutkan ke pengenalan konsep dasar teori ini secara terorganisir.

Definisi 1. Graf adalah himpunan titik-titik yang jumlahnya berhingga, yang disebut simpul-simpul suatu graf, dan garis-garis berpasangan yang menghubungkan beberapa simpul tersebut, yang disebut rusuk-rusuk atau busur-busur dari graf tersebut.

Definisi ini dapat dirumuskan secara berbeda: graf adalah himpunan titik (simpul) dan segmen (sisi) yang tidak kosong, yang kedua ujungnya termasuk dalam himpunan titik tertentu.

Berikut ini kita akan menyatakan simpul-simpul graf tersebut dengan huruf latin A, B, C, D. Terkadang grafik secara keseluruhan dilambangkan dengan satu huruf kapital.

Definisi 2. Simpul suatu graf yang tidak mempunyai sisi mana pun disebut terisolasi.

Definisi 3. Graf yang hanya terdiri dari simpul-simpul terisolasi disebut nol - menghitung .

Notasi: O " – graf dengan simpul yang tidak memiliki sisi

Definisi 4. Graf yang setiap pasangan simpulnya dihubungkan oleh suatu sisi disebut graf lengkap.

Penunjukan: kamu" – graf yang terdiri dari n simpul dan sisi yang menghubungkan semua kemungkinan pasangan simpul tersebut. Grafik seperti itu dapat direpresentasikan sebagai n-gon yang semua diagonalnya digambar

Definisi 5. Derajat suatu simpul adalah banyaknya sisi yang dimiliki simpul tersebut.

Definisi 6. Graf yang semua k simpulnya mempunyai derajat yang sama disebut graf derajat homogen .

Definisi 7. Komplemen suatu graf tertentu adalah graf yang terdiri dari semua sisi dan ujung-ujungnya yang harus dijumlahkan pada graf aslinya untuk memperoleh graf yang lengkap.

Definisi 8. Graf yang dapat direpresentasikan pada suatu bidang sedemikian rupa sehingga sisi-sisinya hanya berpotongan pada titik-titik sudutnya disebut bidang.

Definisi 9. Poligon pada suatu graf planar yang tidak mempunyai simpul atau sisi pada graf tersebut disebut mukanya.

Konsep graf planar dan permukaan graf digunakan ketika memecahkan masalah pewarnaan berbagai peta yang “benar”.

Definisi 10. Jalur A ke X adalah barisan sisi yang mengarah dari A ke X sedemikian rupa sehingga setiap dua sisi yang berdekatan mempunyai titik sudut yang sama, dan tidak ada sisi yang muncul lebih dari satu kali.

Definisi 11. Siklus adalah suatu lintasan yang titik awal dan titik akhirnyanya bertepatan.

Definisi 12. Siklus sederhana adalah siklus yang tidak melalui salah satu simpul pada graf lebih dari satu kali.

Definisi 13. Panjang jalan , diletakkan dalam satu lingkaran , jumlah tepi jalur ini disebut.

Definisi 14. Dua simpul A dan B dalam suatu graf disebut terhubung (terputus) jika ada (tidak ada) lintasan yang mengarah dari A ke B.

Definisi 15. Suatu graf disebut terhubung jika setiap dua simpulnya terhubung; jika suatu graf memuat paling sedikit satu pasang simpul yang tidak terhubung, maka graf tersebut disebut tidak terhubung.

Definisi 16. Pohon adalah graf terhubung yang tidak mengandung siklus.

Model grafik pohon tiga dimensi, misalnya, adalah pohon asli dengan mahkota bercabang yang rumit; sungai dan anak-anak sungainya juga berbentuk pohon, tetapi sudah datar – di permukaan bumi.

Definisi 17. Graf tak terhubung yang seluruhnya terdiri dari pepohonan disebut hutan.

Definisi 18. Pohon yang seluruh n simpulnya diberi nomor dari 1 sampai n disebut pohon dengan simpul yang diberi nomor ulang.

Jadi, kita telah memeriksa definisi dasar teori graf, yang tanpanya mustahil membuktikan teorema, dan, akibatnya, memecahkan masalah.

Masalah diselesaikan dengan menggunakan grafik

Masalah terkenal

Masalah penjual keliling

Masalah travelling salesman merupakan salah satu masalah yang terkenal dalam teori kombinatorik. Itu dikemukakan pada tahun 1934, dan para ahli matematika terbaik mematahkan gigi mereka karenanya.

Rumusan masalahnya adalah sebagai berikut.
Seorang penjual keliling (pedagang pengembara) harus meninggalkan kota pertama, mengunjungi kota 2,1,3..n sekali dalam urutan yang tidak diketahui dan kembali ke kota pertama. Jarak antar kota diketahui. Dalam urutan apa seseorang harus berkeliling kota agar jalur tertutup (tur) penjual keliling menjadi yang terpendek?

Metode untuk memecahkan masalah penjual keliling

Algoritma serakah “pergilah ke kota terdekat (yang belum kamu masuki).”
Algoritme ini disebut “serakah” karena pada langkah terakhir Anda harus membayar mahal untuk keserakahan.
Misalnya jaringan pada gambar [Lampiran Gambar.3], mewakili belah ketupat sempit. Misalkan seorang salesman keliling memulai dari kota 1. Algoritma “pergi ke kota terdekat” akan membawanya ke kota 2, lalu 3, lalu 4; pada langkah terakhir Anda harus membayar keserakahan Anda, kembali sepanjang diagonal panjang berlian. Hasilnya bukan tur terpendek, tapi tur terpanjang.

Masalah tentang jembatan Königsberg.

Masalahnya dirumuskan sebagai berikut.
Kota Koenigsberg terletak di tepi Sungai Pregel dan dua pulau. Berbagai bagian kota dihubungkan oleh tujuh jembatan. Pada hari Minggu, penduduk kota berjalan-jalan di sekitar kota. Pertanyaan: apakah mungkin berjalan-jalan sedemikian rupa sehingga ketika keluar rumah, Anda kembali lagi dengan berjalan tepat satu kali melewati setiap jembatan?
Jembatan yang melintasi Sungai Pregel letaknya seperti pada gambar[Lampiran Gambar.1].

Perhatikan grafik yang sesuai dengan diagram jembatan [Lampiran Gambar 2].

Untuk menjawab pertanyaan soal tersebut, cukup dengan mengetahui apakah graf tersebut termasuk graf Euler. (Jumlah jembatan genap harus memanjang dari setidaknya satu titik). Anda tidak bisa berjalan keliling kota dan menyeberangi semua jembatan satu kali lalu kembali lagi.

Beberapa tugas menarik

1. "Rute".

Masalah 1

Seperti yang Anda ingat, pemburu jiwa yang mati, Chichikov, mengunjungi pemilik tanah terkenal satu kali. Dia mengunjungi mereka dengan urutan sebagai berikut: Manilov, Korobochka, Nozdryov, Sobakevich, Plyushkin, Tentetnikov, Jenderal Betrishchev, Petukh, Konstanzholgo, Kolonel Koshkarev. Sebuah diagram ditemukan di mana Chichikov membuat sketsa posisi relatif perkebunan dan jalan pedesaan yang menghubungkannya. Tentukan tanah milik siapa, jika Chichikov tidak melewati jalan mana pun lebih dari satu kali [Lampiran Gambar 4].

Larutan:

Peta jalan menunjukkan bahwa Chichikov memulai perjalanannya dari perkebunan E, dan diakhiri dengan perkebunan O. Kami mencatat bahwa hanya dua jalan menuju perkebunan B dan C, sehingga Chichikov harus melewati jalan tersebut. Mari kita tandai dengan garis tebal. Bagian dari rute yang melewati A telah diidentifikasi: AC dan AB. Chichikov tidak melakukan perjalanan di jalan AE, AK dan AM. Mari kita coret. Mari kita tandai dengan garis tebal ED; Mari kita coret DK. Mari kita coret MO dan MN; Mari tandai MF dengan garis tebal; coret FO; Mari tandai FH, NK dan KO dengan garis tebal. Mari temukan satu-satunya rute yang mungkin dalam kondisi ini. Dan kita mendapatkan: perkebunan E - milik Manilov, D - Korobochka, C - Nozdryov, A - Sobakevich, B - Plyushkin, M - Tentetnikov, F - Betrishchev, N - Petukh, K - Konstanzholgo, O - Koshkarev [Lampiran Gambar.5].

Masalah 2

Gambar tersebut menunjukkan peta wilayah tersebut [Lampiran Gambar 6].

Anda hanya dapat bergerak sesuai arah panah. Anda dapat mengunjungi setiap titik tidak lebih dari satu kali. Berapa banyak cara yang dapat kamu tempuh dari titik 1 ke titik 9? Rute mana yang terpendek dan mana yang terpanjang.

Larutan:

Kami secara berurutan “mestratifikasi” sirkuit menjadi sebuah pohon, mulai dari simpul 1 [Lampiran Gambar.7]. Ayo ambil pohon. Banyaknya cara yang mungkin untuk berpindah dari 1 sampai 9 sama dengan jumlah simpul “menggantung” pada pohon (ada 14 simpul). Tentunya jalur terpendek adalah 1-5-9; yang terpanjang adalah 1-2-3-6-5-7-8-9.

2 "Grup, kencan"

Masalah 1

Para peserta festival musik, setelah bertemu, bertukar amplop berisi alamat. Buktikan bahwa:

a) jumlah amplop yang diserahkan genap;

b) banyaknya peserta yang menukarkan amplop ganjil adalah genap.

Penyelesaian: Misalkan peserta festival adalah A 1, A 2, A 3. . . , Dan n adalah simpul dari grafik, dan sisi-sisinya menghubungkan pasangan simpul yang mewakili orang-orang yang bertukar amplop [Lampiran Gambar.8]

Larutan:

a) derajat setiap titik sudut A i menunjukkan banyaknya amplop yang diberikan peserta A i kepada temannya. Jumlah total amplop yang ditransmisikan N sama dengan jumlah derajat semua simpul pada grafik N = derajat. Langkah 1+. Sebuah 2++. . . + langkah. Dan -1 + derajat. Dan n, N =2p, di mana p adalah jumlah sisi grafik, yaitu T – genap. Akibatnya, jumlah amplop yang diserahkan genap;

b) dalam persamaan N = derajat. Langkah 1+. Sebuah 2++. . . + langkah. Dan -1 + derajat. Dan n jumlah suku ganjil harus genap, dan ini hanya bisa terjadi jika banyaknya suku ganjil genap. Artinya jumlah peserta yang menukarkan amplop ganjil adalah genap.

Masalah 2

Suatu hari Andrei, Boris, Volodya, Dasha dan Galya setuju untuk pergi ke bioskop pada malam hari. Mereka memutuskan untuk mengoordinasikan pilihan bioskop dan pertunjukan melalui telepon. Diputuskan juga bahwa jika tidak memungkinkan untuk menghubungi seseorang melalui telepon, maka perjalanan ke bioskop akan dibatalkan. Pada malam hari, tidak semua orang berkumpul di bioskop, sehingga kunjungan ke bioskop dibatalkan. Keesokan harinya mereka mulai mencari tahu siapa yang menelepon siapa. Ternyata Andrey menelepon Boris dan Volodya, Volodya menelepon Boris dan Dasha, Boris menelepon Andrey dan Dasha, Dasha menelepon Andrey dan Volodya, dan Galya menelepon Andrey, Volodya dan Boris. Siapa yang tidak bisa menelepon dan karena itu tidak datang ke pertemuan?

Larutan:

Mari kita menggambar lima titik dan memberi label dengan huruf A, B, C, D, D. Ini adalah huruf pertama dari namanya. Mari kita hubungkan titik-titik yang sesuai dengan nama orang yang menelepon.

[Lampiran Gambar.9]

Dari gambar tersebut terlihat jelas bahwa masing-masing pria - Andrey, Boris, dan Volodya - menelepon yang lainnya. Itu sebabnya orang-orang ini datang ke bioskop. Namun Galya dan Dasha tidak bisa saling bertelepon (titik G dan E tidak dihubungkan oleh suatu ruas garis) sehingga sesuai kesepakatan, tidak datang ke bioskop.

Penerapan grafik dalam berbagai bidang kehidupan masyarakat

Selain contoh yang diberikan, grafik banyak digunakan dalam konstruksi, teknik elektro, manajemen, logistik, geografi, teknik mesin, sosiologi, pemrograman, otomatisasi proses dan produksi teknologi, psikologi, dan periklanan. Jadi, dari uraian di atas, tidak dapat disangkal nilai praktis teori graf, yang pembuktiannya menjadi tujuan penelitian ini.

Dalam bidang ilmu pengetahuan dan teknologi apa pun Anda menjumpai grafik. Grafik adalah objek matematika luar biasa yang dapat digunakan untuk memecahkan masalah matematika, ekonomi dan logika, berbagai teka-teki, dan menyederhanakan kondisi masalah dalam fisika, kimia, elektronik, dan otomasi. Banyak fakta matematika yang dapat dengan mudah dirumuskan dalam bahasa grafik. Teori grafik adalah bagian dari banyak ilmu pengetahuan. Teori graf adalah salah satu teori matematika yang paling indah dan visual. Baru-baru ini, teori graf semakin banyak diterapkan dalam isu-isu terapan. Bahkan kimia komputasi telah muncul - bidang kimia yang relatif muda berdasarkan penerapan teori grafik.

Grafik molekul, digunakan dalam stereokimia dan topologi struktural, kimia cluster, polimer, dll., adalah grafik tidak berarah yang menampilkan struktur molekul [Lampiran Gambar 10]. Simpul dan tepi grafik ini berhubungan dengan atom-atom yang bersesuaian dan ikatan kimia di antara keduanya.

Grafik molekul dan pohon: [Lampiran Gambar 10] a, b - masing-masing multigraf. etilen dan formaldehida; mereka bilang isomer pentana (pohon 4, 5 isomorfik terhadap pohon 2).

Dalam stereokimia organisme yang paling banyak. Pohon molekul sering digunakan - pohon utama grafik molekuler, yang hanya berisi semua simpul yang bersesuaian dengan atom C. Kompilasi kumpulan mol. pohon dan penetapan isomorfismenya memungkinkan untuk menentukan apa yang dikatakannya. struktur dan temukan jumlah total isomer alkana, alkena, dan alkuna

Jaringan protein

Jaringan protein adalah sekelompok protein yang berinteraksi secara fisik yang berfungsi bersama-sama dan terkoordinasi dalam sel, mengendalikan proses yang saling berhubungan yang terjadi di dalam tubuh. [gambar lampiran. sebelas].

Grafik sistem hierarki disebut pohon. Ciri khas pohon adalah hanya ada satu jalur antara dua simpulnya. Pohon tidak mengandung siklus atau loop.

Biasanya, pohon yang mewakili sistem hierarki memiliki satu simpul utama, yang disebut akar pohon. Setiap simpul pohon (kecuali akar) hanya memiliki satu leluhur - objek yang ditunjuk olehnya termasuk dalam satu kelas tingkat atas. Setiap simpul dari sebuah pohon dapat menghasilkan beberapa keturunan - simpul yang sesuai dengan kelas-kelas di tingkat yang lebih rendah.

Untuk setiap pasangan simpul pohon, terdapat jalur unik yang menghubungkannya. Sifat ini digunakan ketika menemukan semua nenek moyang, misalnya dalam garis keturunan laki-laki, dari setiap orang yang silsilahnya direpresentasikan dalam bentuk silsilah keluarga, yaitu “pohon” dalam pengertian teori graf.

Contoh silsilah keluarga saya [Lampiran Gambar 12].

Satu contoh lagi. Gambar menunjukkan silsilah keluarga alkitabiah [Lampiran Gambar 13].

Penyelesaian masalah

1. Tugas transportasi. Biarkan ada pangkalan di kota Krasnodar dengan bahan mentah yang perlu didistribusikan ke kota Krymsk, Temryuk, Slavyansk-on-Kuban dan Timashevsk dalam satu perjalanan, menghabiskan waktu dan bahan bakar sesedikit mungkin dan kembali ke Krasnodar .

Larutan:

Pertama, mari kita buat grafik semua kemungkinan rute perjalanan [Lampiran Gambar.14], dengan mempertimbangkan jalan sebenarnya antara pemukiman ini dan jarak di antara mereka. Untuk mengatasi masalah ini, kita perlu membuat grafik lain yang mirip pohon [Lampiran Gambar.15].

Untuk kenyamanan solusi, kami menetapkan kota dengan nomor: Krasnodar - 1, Krymsk - 2, Temryuk - 3, Slavyansk - 4, Timashevsk - 5.

Hasilnya adalah 24 solusi, tapi kita hanya membutuhkan jalur terpendek. Dari seluruh solusi, hanya dua yang memuaskan, yaitu 350 km.

Demikian pula, adalah mungkin dan, menurut saya, perlu untuk menghitung transportasi nyata dari satu lokasi ke lokasi lain.

Masalah logis yang melibatkan transfusi. Ember tersebut berisi air sebanyak 8 liter, dan terdapat dua buah panci berkapasitas 5 dan 3 liter. Anda perlu menuangkan 4 liter air ke dalam panci lima liter dan menyisakan 4 liter di dalam ember, yaitu tuangkan air secara merata ke dalam ember dan panci besar.

Larutan:

Situasi setiap saat dapat digambarkan dengan tiga angka [Lampiran Gambar 16].

Hasilnya, kita mendapatkan dua solusi: satu dalam 7 gerakan, yang lain dalam 8 gerakan.

Kesimpulan

Jadi, untuk mempelajari cara memecahkan masalah, Anda perlu memahami apa itu masalah, bagaimana strukturnya, terdiri dari komponen apa, alat apa yang dapat digunakan untuk memecahkan masalah.

Memecahkan masalah praktis dengan menggunakan teori graf, menjadi jelas bahwa dalam setiap langkah, dalam setiap tahap penyelesaiannya, perlu diterapkan kreativitas.

Sejak awal, pada tahap pertama, terletak pada kenyataan bahwa Anda harus mampu menganalisis dan mengkodekan kondisi masalah. Tahap kedua adalah notasi skema, yang terdiri dari representasi geometris dari grafik, dan pada tahap ini unsur kreativitas sangat penting karena tidak mudah untuk menemukan korespondensi antara unsur-unsur kondisi dan unsur-unsur yang bersesuaian. grafik.

Saat menyelesaikan masalah transportasi atau tugas menggambar silsilah keluarga, saya sampai pada kesimpulan bahwa metode grafik tentu saja menarik, indah, dan visual.

Saya menjadi yakin bahwa grafik banyak digunakan di bidang ekonomi, manajemen, dan teknologi. Teori grafik juga digunakan dalam pemrograman. Hal ini tidak dibahas dalam makalah ini, tapi menurut saya ini hanya masalah waktu saja.

Karya ilmiah ini mengkaji grafik matematika, bidang penerapannya, dan menyelesaikan beberapa permasalahan dengan menggunakan grafik. Pengetahuan tentang dasar-dasar teori graf diperlukan dalam berbagai bidang yang berkaitan dengan produksi dan manajemen bisnis (misalnya, jadwal pembangunan jaringan, jadwal pengiriman surat). Selain itu, saat mengerjakan karya ilmiah, saya menguasai pengerjaan komputer dengan menggunakan editor teks WORD. Dengan demikian, tujuan karya ilmiah telah tercapai.

Jadi, dari uraian di atas, nilai praktis teori graf tidak dapat disangkal, yang pembuktiannya merupakan tujuan dari pekerjaan ini.

literatur

Berge K. Teori graf dan penerapannya. -M.: IIL, 1962.

Kemeny J., Snell J., Thompson J. Pengantar matematika terbatas. -M.: IIL, 1963.

Oreo. Grafik dan penerapannya. -M.: Mir, 1965.

Harari F. Teori grafik. -M.: Mir, 1973.

Zykov A.A. Teori grafik terbatas. -Novosibirsk: Sains, 1969.

Berezina L.Yu. Grafik dan penerapannya. -M.: Pendidikan, 1979. -144 hal.

"Jurnal Pendidikan Soros" No. 11 1996 (artikel "Grafik Datar");

Gardner M. "Kenyamanan matematika", M. "Dunia", 1972 (bab 35);

Olehnik S. N., Nesterenko Yu. V., Potapov M. K. “Masalah menghibur lama”, M. “Sains”, 1988 (bagian 2, bagian 8; lampiran 4);

Aplikasi