Buku karya K. Berge adalah buku pertama tentang teori graf dalam bahasa Rusia. Sementara itu, dalam beberapa tahun terakhir, minat terhadap teori ini meningkat tajam baik di kalangan ahli matematika maupun perwakilan dari berbagai disiplin ilmu. Hal ini dijelaskan oleh fakta bahwa metode teori graf berhasil memecahkan berbagai permasalahan dalam teori rangkaian listrik, teori rantai transpor, teori informasi, sibernetika, dll.
Dalam buku Berge, teori graf disajikan secara berurutan, dimulai dari dasar. Diasumsikan bahwa pembaca memiliki pengetahuan matematika yang sangat sederhana, meskipun ia memiliki budaya matematika tertentu. Teksnya memuat banyak contoh, seringkali lucu. Buku ini dapat digunakan untuk kajian awal teori graf. Matematikawan profesional juga akan menemukan banyak hal menarik di dalamnya.

Algoritma untuk mengidentifikasi siklus Euler secara langsung.
[Fleury]. Mari kita perhatikan multigraf G yang terhubung, yang semua simpulnya memiliki derajat genap, dan kita akan mencoba menggambarnya dengan satu pukulan, tanpa menggunakan koreksi pada bagian lintasan yang sudah digambar selama proses konstruksi. Cukup dengan mengikuti aturan berikut:
1 Kita keluar dari titik sembarang a; Kami mencoret setiap tepi yang dilewati.
2 Kita tidak pernah melewati sisi seperti itu dan, yang pada saat ini dianggap sebagai tanah genting (yaitu, jika dihilangkan, grafik yang dibentuk oleh sisi yang tidak bersilangan akan terbagi menjadi dua komponen terhubung yang masing-masing memiliki setidaknya satu sisi),

Dengan mengikuti aturan ini, kita akan selalu berada pada posisi yang menguntungkan, karena ketika kita berada di x = a, grafik (sisi yang tidak bersilangan) memiliki dua simpul berderajat ganjil: x dan a; jika simpul-simpul terisolasi dibuang, maka graf terhubung tetap ada, yang berdasarkan Teorema 1, memiliki rantai Euler yang dimulai dari x.

Isi
Perkenalan
Bab 1. Definisi dasar
Himpunan dan pemetaan multinilai
Grafik. Jalur dan kontur
Sirkuit dan siklus
Bab 2. Kajian Pendahuluan Keteraturan Semu
Urutan kuasi ditentukan oleh grafik
Grafik dan basis induktif
Bab 3. Fungsi dan Fungsi Ordinal
Grundy untuk grafik tak terbatas
Pertimbangan umum mengenai grafik tak hingga
Fungsi biasa
Fungsi kasar
Operasi pada grafik
Bab 4. Bilangan dasar teori graf
Nomor siklomatik
Nomor berwarna
Nomor stabilitas internal
Nomor stabilitas eksternal
Bab 5. Kernel Grafik
Teorema keberadaan dan keunikan
Aplikasi untuk fungsi Grundy
Bab 6. Permainan Grafik
Permainan Nim
Definisi umum permainan (dengan informasi lengkap)
Strategi
Bab 7. Masalah Jalur Terpendek
Proses demi tahapan Beberapa generalisasi
Bab 8. Jaringan transportasi
Masalah Aliran Maksimum Masalah Aliran Terkecil
Masalah Aliran yang Kompatibel dengan Set-Value
Jaringan transportasi tanpa akhir
Bab 9. Teorema setengah pangkat
Semi derajat keluar dan masuk
Bab 10. Mencocokkan grafik sederhana
Masalah pencocokan maksimum
Defisiensi grafik sederhana
Algoritma Hongaria
Generalisasi ke kasus yang tak terbatas
Penerapan teori matriks
Bab 11. Faktor
Jalur Hamilton dan kontur Hamilton
Menemukan faktor
Menemukan grafik parsial dengan setengah derajat tertentu
Bab 12. Pusat Grafik
Pusat
Radius
Bab 13. Diameter graf terhubung kuat
Sifat umum graf terhubung kuat tanpa loop
Diameter
Bab 14. Grafik Matriks Ketetanggaan
Penerapan operasi matriks konvensional
Menghitung masalah
Masalah pemimpin
Menggunakan Operasi Boolean
Bab 15. Matriks insiden
Matriks yang sepenuhnya unimodular
Sistem yang sepenuhnya unimodular
Matriks siklomatik
Bab 16. Pohon dan Pohon Nenek Moyang
Pohon
Penelitian analitis
pohon besar
Bab 17. Masalah Euler
Siklus Euler Kontur Euler
Bab 18. Mencocokkan grafik sembarang
Teori Sirkuit Bolak-balik
Menemukan graf parsial dengan derajat simpul tertentu
Pencocokan sempurna
Penerapan pada nomor stabilitas internal
Bab 19. Faktoroid
Siklus Hamilton dan faktoroid
Syarat perlu dan syarat cukup bagi adanya faktoroid
Bab 20. Konektivitas Grafik
Poin artikulasi
Grafik tanpa artikulasi
grafik terhubung-h
Bab 21. Grafik planar
Properti dasar
Generalisasi
Tambahan
I. Di luar teori umum, permainan
II. Tentang tugas transportasi
AKU AKU AKU. Tentang penerapan konsep potensial dalam jaringan transportasi
IV. Masalah yang belum terpecahkan dan asumsi yang belum terbukti
V. Tentang beberapa prinsip dasar berhitung (J. Riguet)
VI. Tambahan pada terjemahan bahasa Rusia (A.A. Zykov dan G.I. Kozhukhin)
Literatur
Teori grafik dan buku C. Berge (kata penutup untuk terjemahan bahasa Rusia)
Indeks karakter
Indeks nama
Indeks subjek.

Unduh e-book secara gratis dalam format yang nyaman, tonton dan baca:
Download buku Teori Graf dan Penerapannya, Berge K. - fileskachat.com, download cepat dan gratis.

Grafik adalah topik yang menyenangkan, bermanfaat, dan menakutkan. Teori Grafik - "Horor Siswa". Algoritme grafik adalah hasil pemikiran menakjubkan dari orang-orang yang menemukannya.

Apa itu grafik? Untuk menjawab pertanyaan pembaca saya ini, saya akan menjelaskan topiknya sedikit berbeda.
Grafik adalah sekumpulan objek.
Dalam sebagian besar soal, ini adalah objek dengan tipe yang sama. (Banyak kota, atau banyak rumah, atau banyak orang, atau banyak hal lain yang sejenis)

Untuk menyelesaikan masalah dengan himpunan seperti itu, Anda perlu menetapkan setiap objek dari himpunan ini sebagai sesuatu. Secara umum diterima untuk menyebut hal ini sebagai simpul suatu graf.

Lebih mudah untuk mendeskripsikan grafik dan definisi dasar dengan gambar, jadi gambar harus disertakan untuk membaca halaman ini.

Seperti yang saya tulis sebelumnya, grafik adalah sekumpulan objek. Benda-benda ini biasanya memiliki tipe yang sama. Cara termudah untuk memberi contoh adalah di perkotaan. Masing-masing dari kita tahu apa itu kota dan apa itu jalan raya. Masing-masing dari kita tahu bahwa mungkin ada atau tidak ada jalan menuju kota. Secara umum, setiap kumpulan objek dapat dikarakterisasi sebagai grafik.

Jika kita berbicara tentang grafik sebagai kota, maka jalan dapat dibangun antar kota, atau dapat dihancurkan di suatu tempat, tidak dibangun, atau kota tersebut umumnya terletak di pulau, tidak ada jembatan, dan yang menarik hanyalah jalan beraspal. . Terlepas dari kenyataan bahwa tidak ada jalan menuju kota seperti itu, kota ini dapat dimasukkan ke dalam banyak objek yang dianalisis, dan semua objek yang digabungkan membentuk kumpulan objek atau, lebih sederhananya, grafik.

Pasti Anda pernah membaca buku teks dan melihat notasi G(V,E) atau sejenisnya. Jadi, V adalah suatu benda dari seluruh himpunan benda. Dalam kasus kita, himpunan objek adalah kota, oleh karena itu, V adalah kota tertentu. Karena objek belum tentu kota, dan kata objek dapat membingungkan, objek dari himpunan tersebut dapat disebut titik, titik, atau sesuatu yang lain, tetapi paling sering disebut titik puncak grafik dan dilambangkan dengan huruf V.
Dalam pemrograman, ini biasanya berupa kolom atau baris dari array dua dimensi, dimana array tersebut disebut matriks ketetanggaan atau matriks kejadian.

Dalam literatur, di Internet, dan secara umum di mana pun sesuatu ditulis tentang grafik, Anda akan menemukan konsep seperti busur dan tepi. Gambar ini menunjukkan tepi grafik. Itu. ini adalah tiga sisi E1, E2 dan E3.

Busur dan tepi berbeda karena tepi merupakan sambungan dua arah. Dia menginginkannya, dia pergi ke tetangganya, dia menginginkannya, dia kembali dari tetangganya. Jika kurang jelas, Anda bisa membayangkan sebuah rumah, lapangan terbang, pesawat terbang, dan penerjun payung. Seorang skydiver dapat berangkat dari rumahnya menuju ke lapangan terbang, namun sesampainya di lapangan terbang, ingatlah bahwa ia lupa parasut keberuntungannya di rumah, lalu kembali ke rumah dan mengambil parasut tersebut. — Jalan yang dapat dilalui bolak-balik disebut tepi.
Jika seorang penerjun payung berada di dalam pesawat dan sedang melompat dari pesawat, namun penerjun payung tersebut lupa memasang parasut keberuntungannya di dalam pesawat, apakah penerjun payung tersebut dapat mengambil apa yang ia lupa? Lintasan yang hanya menuju satu arah disebut busur. Biasanya kita mengatakan bahwa sebuah sisi menghubungkan dua simpul, dan sebuah busur berpindah dari satu simpul ke simpul lainnya.

Pada gambar ini, grafiknya hanya memiliki busur. Busur pada grafik ditandai dengan panah, karena arah yang dapat diakses sangat jelas. Jika suatu graf hanya terdiri dari busur-busur tersebut, maka graf tersebut disebut berarah.

Anda akan sering menjumpai konsep kedekatan dan kejadian. Pada gambar, dua sisi yang menuju satu titik ditandai dengan warna merah. Tepi seperti itu, seperti simpul yang dijelaskan di atas, juga disebut berdekatan.

Banyak yang tidak dijelaskan, namun informasi ini mungkin dapat membantu seseorang.

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. Menyelesaikan 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 masalah 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 melakukannya 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 ditanya 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 nomor tersebut 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 ganjil. cukup untuk memecahkan masalah tersebut. Ketika hal ini ditentukan, kami 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 pada suatu graf, dan garis-garis berpasangan yang menghubungkan beberapa simpul tersebut, yang disebut sisi-sisi atau busur-busur pada graf tersebut.

Definisi ini dapat dirumuskan secara berbeda: graf adalah himpunan titik (simpul) dan segmen (tepi) 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 tidak 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 kita tandai dengan garis tebal MF; 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: a, b - masing-masing multigraf. etilen dan formaldehida; kata mereka 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 pembentukan isomorfismenya memungkinkan untuk menentukan katanya. 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. 11].

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].

Contoh lain. Gambar menunjukkan silsilah keluarga alkitabiah [Lampiran Gambar 13].

Pemecahan 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 berukuran 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.

Bijih O. 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

Beras. 6

Beras. 7

Beras. 8

aplikasi

Aplikasi

Beras. 14

aplikasi

Aplikasi

UNIVERSITAS PEDAGOGIS NEGARA VLADIMIR

ABSTRAK

"TEORI GRAFIK"

Selesai:

Zudina T.V.

Vladimir 2001

1. Pendahuluan

2. Sejarah teori graf

3. Definisi dasar teori graf

4. Teorema dasar teori graf

5. Permasalahan penerapan teori graf

6. Penerapan teori graf dalam mata kuliah matematika sekolah

7. Penerapan teori graf dalam berbagai bidang ilmu pengetahuan dan teknologi

8. Kemajuan terkini dalam teori graf

§1. SEJARAH MUNCULNYA TEORI GRAFIK.

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

“Saya pernah ditanya masalah tentang sebuah pulau yang terletak di kota Königsberg dan dikelilingi oleh sungai yang dilintasi tujuh jembatan. Pertanyaannya adalah apakah ada orang yang bisa mengitarinya terus menerus, hanya melewati satu kali melalui setiap jembatan diberitahu bahwa tidak seorang pun Saya masih belum mampu melakukan ini, tetapi tidak ada yang membuktikan bahwa ini tidak mungkin. Pertanyaan ini, meskipun sepele, bagi saya tampaknya patut mendapat perhatian karena baik geometri, aljabar, maupun seni kombinatorial tidak cukup untuk melakukannya. selesaikan... Setelah berpikir panjang, saya menemukan aturan yang mudah, berdasarkan bukti yang sepenuhnya meyakinkan, dengan bantuan yang memungkinkan untuk segera menentukan dalam semua masalah semacam ini apakah jalan memutar seperti itu dapat dilakukan melalui sejumlah masalah. jembatan terletak dengan cara apapun, atau apakah jembatan Königsberg tidak dapat ditemukan sehingga dapat direpresentasikan dalam gambar berikut[gbr.1] , di mana A menunjukkan sebuah pulau, dan B , C dan D - bagian benua yang dipisahkan satu sama lain oleh cabang sungai. Tujuh jembatan ditandai dengan huruf A , B , C , D , e , F , G ".

(GAMBAR 1.1)

Mengenai metode yang ditemukannya untuk memecahkan masalah semacam ini, Euler menulis [lihat. hal.102-104]:

“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 -. A , B , C , D . Hal berikutnya yang perlu dibedakan adalah apakah jumlah jembatan yang menuju ke masing-masing ruas tersebut genap atau ganjil. Jadi, dalam kasus kita, lima jembatan mengarah ke bagian A, dan tiga jembatan masing-masing mengarah ke bagian lainnya, mis. Jumlah jembatan yang menuju ke masing-masing bagian adalah ganjil, dan ini saja sudah cukup untuk menyelesaikan masalah. Setelah hal ini ditentukan, kami menerapkan aturan berikut: jika jumlah jembatan yang menuju ke masing-masing bagian adalah genap, maka jalan memutar yang dimaksud dapat dilakukan, dan pada saat yang sama, jalan memutar ini dapat dimulai dari bagian mana pun. . Jika dua dari angka-angka ini ganjil, karena hanya satu yang tidak boleh ganjil, maka transisi dapat terjadi, seperti yang ditentukan, tetapi hanya permulaan rangkaian yang harus diambil dari salah satu dari dua bagian yang ke mana angka ganjil itu mengarah. jembatan. 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." .

Dasar pemikiran aturan di atas dapat ditemukan dalam surat L. Euler kepada temannya Ehler tertanggal 3 April tahun yang sama. Kami akan menceritakan kembali di bawah kutipan surat ini.

Ahli matematika itu menulis bahwa peralihan itu mungkin terjadi jika pada bagian pertigaan sungai tidak ada lebih dari dua daerah yang dituju oleh jumlah jembatan ganjil. Untuk memudahkan membayangkannya, kita akan menghapus jembatan yang sudah dilalui pada gambar. Sangat mudah untuk memeriksa bahwa jika kita mulai bergerak sesuai dengan aturan Euler, melintasi satu jembatan dan menghapusnya, maka gambar tersebut akan menunjukkan bagian di mana lagi-lagi tidak ada lebih dari dua area yang dituju oleh jumlah jembatan ganjil, dan jika ada adalah daerah dengan jumlah jembatan ganjil kita akan berlokasi di salah satunya. Terus bergerak seperti ini, kita akan melintasi semua jembatan satu kali.

Kisah jembatan kota Königsberg memiliki kelanjutan modern. Mari kita buka, misalnya, buku pelajaran matematika sekolah yang diedit oleh N.Ya. Vilenkina untuk kelas enam. Di dalamnya, di halaman 98, dengan judul pengembangan perhatian dan kecerdasan, kita akan menemukan masalah yang berhubungan langsung dengan masalah yang pernah dipecahkan Euler.

Soal No.569. Terdapat tujuh pulau di danau ini yang saling terhubung seperti terlihat pada Gambar 1.2. Pulau manakah yang harus dituju oleh perahu agar mereka dapat melintasi setiap jembatan dan hanya sekali? Mengapa wisatawan tidak bisa diangkut ke pulau itu? A ?

(GAMBAR 1.2)

Larutan. Karena permasalahan ini mirip dengan permasalahan jembatan Königsberg, maka dalam penyelesaiannya kita juga akan menggunakan aturan Euler. Hasilnya, kami mendapat jawaban sebagai berikut: perahu harus mengantarkan pelancong ke pulau itu E atau F sehingga mereka dapat melintasi setiap jembatan satu kali. Dari aturan Euler yang sama, jalan memutar yang diperlukan tidak mungkin dilakukan jika dimulai dari pulau A .

Sebagai kesimpulan, kami mencatat bahwa masalah jembatan Königsberg dan masalah serupa, bersama dengan seperangkat metode untuk mempelajarinya, merupakan cabang matematika yang sangat penting dalam istilah praktis, yang disebut teori graf. Karya pertama tentang grafik adalah milik L. Euler dan muncul pada tahun 1736. Selanjutnya, Koenig (1774-1833), Hamilton (1805-1865), dan matematikawan modern C. Berge, O. Ore, A. Zykov mengerjakan grafik.

§2. TEOREMA DASAR TEORI GRAFIK

Teori graf, sebagaimana disebutkan di atas, 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 2.01. Menghitung adalah kumpulan sejumlah titik berhingga yang disebut puncak grafik, dan garis berpasangan yang menghubungkan beberapa simpul tersebut, disebut tulang rusuk atau busur grafik.

Definisi ini dapat dirumuskan secara berbeda: menghitung disebut himpunan titik tak kosong ( puncak) dan segmen ( tulang rusuk), yang kedua ujungnya termasuk dalam himpunan titik tertentu (lihat Gambar 2.1).

(GAMBAR 2.1)

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

Definisi 2.02. Simpul-simpul suatu graf yang tidak termasuk dalam suatu sisi disebut terpencil .

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

Penamaan: HAI " – graf dengan simpul yang tidak memiliki sisi (Gbr. 2.2).

(GAMBAR 2.2)

Definisi 2.04. Graf yang setiap pasang simpulnya dihubungkan oleh sebuah sisi disebut menyelesaikan .

Penamaan: kamu " – grafik yang terdiri dari N simpul dan sisi yang menghubungkan semua kemungkinan pasangan simpul tersebut. Grafik seperti itu dapat direpresentasikan sebagai N– segitiga yang semua diagonalnya digambar (Gbr. 2.3).

(GAMBAR 2.3)

Definisi 2.05. Derajat puncak adalah jumlah sisi yang dimiliki suatu titik.

Penamaan: P (A) – derajat simpul A . Misalnya pada Gambar 2.1: P (A)=2, P (B)=2, P (C)=2, P (D)=1, P (E)=1.

Definisi 2.06. Hitung, derajat semuanya k yang simpul-simpulnya identik disebut homogen menghitung derajat k .

Gambar 2.4 dan 2.5 menunjukkan grafik homogen derajat kedua dan ketiga.

(GAMBAR 2.4 dan 2.5)

Definisi 2.07. Suplemen diberikan grafik adalah graf yang terdiri dari semua sisi dan ujung-ujungnya yang harus dijumlahkan pada graf aslinya agar diperoleh graf yang lengkap.

Gambar 2.6 menunjukkan grafik aslinya G , terdiri dari empat simpul dan tiga segmen, dan pada Gambar 2.7 - komplemen dari grafik ini - grafik G " .

(GAMBAR 2.6 dan 2.7)

Kita melihat bahwa pada Gambar 2.5 terdapat tulang rusuk AC Dan BD berpotongan di suatu titik yang bukan merupakan titik puncak grafik. Namun ada kalanya suatu graf tertentu perlu direpresentasikan pada suatu bidang sedemikian rupa sehingga sisi-sisinya hanya berpotongan di titik-titiknya (masalah ini akan dibahas secara rinci lebih lanjut, di paragraf 5).

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

Misalnya, Gambar 2.8 menunjukkan grafik planar yang isomorfik (sama) dengan grafik pada Gambar 2.5. Namun perlu diperhatikan bahwa tidak semua graf adalah planar, meskipun yang terjadi adalah kebalikannya, yaitu graf planar apa pun dapat direpresentasikan dalam bentuk biasa.

(GAMBAR 2.8)

Definisi 2.09. Poligon pada suatu graf planar yang tidak mempunyai titik atau sisi pada graf tersebut disebut tepian .

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 ini juga membahas permasalahan yang lebih kompleks yang mungkin menarik bagi mahasiswa 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.
J. A. Bondy, U. S. R. Murty. Teori Grafik. Pegas, 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 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.

Interaksi antara manusia dan teknosfer

Bagaimana titik sudut suatu segitiga ditentukan?