Teori graf: konsep dasar dan tugas. Grafik sebagai struktur data. Penerapan praktis teori graf Signifikansi teori graf

1736, Koenigsberg. Sungai Pregelya mengalir melalui kota. Terdapat tujuh jembatan di kota ini, letaknya seperti terlihat pada gambar di atas. Sejak zaman kuno, penduduk Königsberg bergelut dengan teka-teki: mungkinkah melintasi semua jembatan, hanya melintasi masing-masing jembatan satu kali? Masalah ini diselesaikan baik secara teoritis, di atas kertas, dan dalam praktiknya, dengan berjalan kaki - melewati jembatan-jembatan ini. Tidak ada yang bisa membuktikan bahwa ini tidak mungkin, tapi tidak ada yang bisa melakukan perjalanan “misterius” melintasi jembatan.

Matematikawan terkenal Leonhard Euler berhasil memecahkan masalah tersebut. Selain itu, dia tidak hanya memecahkan masalah khusus ini, tetapi juga menemukan metode umum untuk memecahkan masalah serupa. Ketika memecahkan masalah jembatan Königsberg, Euler melanjutkan sebagai berikut: dia “memampatkan” tanah menjadi titik-titik, dan “meregangkan” jembatan menjadi garis-garis. Bangun yang terdiri dari titik-titik dan garis yang menghubungkan titik-titik tersebut disebut MENGHITUNG.

Graf adalah himpunan himpunan simpul tak kosong dan hubungan antar simpul. Lingkaran disebut simpul pada suatu graf, garis dengan panah disebut busur, dan garis tanpa panah disebut tepi.

Jenis grafik:

1. Grafik terarah(secara singkat dwihuruf) - yang ujung-ujungnya diberi arah.

2. Grafik tidak berarah adalah grafik yang tidak mempunyai arah garis.

3. Grafik berbobot– busur atau tepi memiliki bobot (informasi tambahan).

Memecahkan masalah menggunakan grafik:

Tugas 1.

Solusi: Mari kita nyatakan ilmuwan sebagai simpul dari grafik dan tarik garis dari setiap simpul ke empat simpul lainnya. Kami mendapatkan 10 baris, yang akan dianggap jabat tangan.

Tugas 2.

Ada 8 pohon yang tumbuh di lokasi sekolah: pohon apel, poplar, birch, rowan, oak, maple, larch, dan pinus. Rowan lebih tinggi dari larch, pohon apel lebih tinggi dari maple, oak lebih rendah dari birch, tetapi lebih tinggi dari pinus, pinus lebih tinggi dari rowan, birch lebih rendah dari poplar, dan larch lebih tinggi dari pohon apel. Susunlah pohon-pohon dari yang terpendek hingga yang tertinggi.

Larutan:

Titik-titik pada graf tersebut berupa pohon, ditandai dengan huruf pertama nama pohon. Ada dua hubungan dalam tugas ini: “menjadi lebih rendah” dan “menjadi lebih tinggi”. Pertimbangkan hubungan “menjadi lebih rendah” dan gambarlah panah dari pohon yang lebih rendah ke pohon yang lebih tinggi. Kalau soalnya abu gunung lebih tinggi dari larch, maka kita pasang anak panah dari larch ke abu gunung, dan seterusnya. Kita mendapatkan grafik yang menunjukkan bahwa pohon terpendek adalah maple, diikuti oleh apel, larch, rowan, pinus, oak, birch, dan poplar.

Tugas 3.

Natasha mempunyai 2 amplop: biasa dan udara, dan 3 perangko: persegi panjang, persegi dan segitiga. Ada berapa cara Natasha memilih amplop dan prangko untuk mengirim surat?

Larutan:

Di bawah ini adalah rincian tugas-tugasnya.

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 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 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, hukum apa pun 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 jalur lain dari satu ke yang lain, kecuali melalui jembatan.Dalam contoh ini, 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 menuju ke bagian A, dan tiga jembatan masing-masing ke bagian lainnya, yaitu Jumlah jembatan yang menuju ke masing-masing bagian adalah ganjil, dan ini saja sudah cukup. untuk memecahkan masalah tersebut. Setelah hal ini ditentukan, kami menerapkan aturan berikut: jika jumlah jembatan yang menuju ke masing-masing bagian adalah genap, maka jalan memutar tersebut dapat dilakukan, dan pada saat yang sama, hal ini dapat dimulai. jalan memutar dari bagian mana pun. Namun, 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 bidang 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 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 memanggil Boris dan Volodya, Volodya memanggil Boris dan Dasha, Boris memanggil Andrey dan Dasha, Dasha memanggil Andrey dan Volodya, dan Galya memanggil 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 molekul, yang hanya berisi semua simpul yang bersesuaian dengan atom C. Kompilasi himpunan 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 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 graf 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. “Science”, 1988 (bagian 2, bagian 8; lampiran 4);

Aplikasi

Beras. 6

Beras. 7

Beras. 8

aplikasi

Aplikasi

Beras. 14

aplikasi

Aplikasi

Di antara masalah-masalah yang terkait dengan pemecahan masalah logis, perhatian para peneliti dalam beberapa tahun terakhir tertuju pada pertanyaan tentang penerapan teori graf pada jenis masalah ini.

Teori graf saat ini merupakan cabang matematika diskrit yang berkembang secara intensif. Hal ini disebabkan oleh banyaknya objek dan situasi yang digambarkan dalam bentuk model grafik: jaringan komunikasi, rangkaian perangkat listrik dan elektronik, molekul kimia, hubungan antar manusia, dan masih banyak lagi.

Tugas grafik memiliki sejumlah keunggulan yang memungkinkannya digunakan untuk mengembangkan imajinasi dan meningkatkan pemikiran logis. Masalah grafik dapat disajikan dalam bentuk yang menghibur dan menyenangkan.

Subyek penelitian dalam karya ini adalah penyelesaian masalah logika dengan menggunakan grafik.

Tujuan penelitian: menerapkan peralatan grafik untuk memecahkan masalah logika.

Hipotesa: Menurut pendapat kami, menyelesaikan banyak masalah logika tidak akan memakan banyak tenaga, kami akan menggunakan teori grafik untuk ini.

Tujuan penelitian:

pertimbangkan untuk memecahkan masalah menggunakan grafik;

belajar menerjemahkan masalah ke dalam bahasa grafik;

membandingkan metode pemecahan masalah tradisional dengan metode teori graf.

Pada tahun 1736, matematikawan besar Leonhard Euler menemukan solusi atas teka-teki yang disebut Masalah Jembatan Königsberg. Sungai Pregel, mengalir melalui Kaliningrad (sebelumnya kota ini disebut Königsberg) menyapu dua pulau (Gbr. Gambar 1 Gambar 1). Pada masa Euler, tepian sungai dan pulau-pulau dihubungkan oleh jembatan seperti terlihat pada gambar. Teka-teki tersebut membutuhkan pencarian rute yang melewati keempat daratan satu kali, dan akhir serta awal jalan harus bertepatan.

Gambar 1

L. Euler membuktikan bahwa tidak ada rute yang memenuhi kondisi teka-teki tersebut, dan mengembangkan teori untuk memecahkan teka-teki semacam ini. Mengetahui materi pada bagian pendahuluan mata kuliah “Pengantar Grafik” tidaklah sulit untuk mereproduksi gagasan penalaran L. Euler. Untuk melakukan hal ini, pertama-tama Anda harus mengganti Gambar 1 dengan diagram yang ditunjukkan pada Gambar 2, di mana pulau dan pantai diwakili oleh titik-titik.

Gambar 2

Diagram yang ditunjukkan pada Gambar 2 sebenarnya bukanlah sebuah grafik: ia memiliki banyak sisi. Namun, tahun 1736, ketika teka-teki ini terpecahkan, secara umum dianggap sebagai tahun lahirnya teori graf.

Lebih dari seratus tahun kemudian, pada tahun 1874, ilmuwan Jerman G. Kirchhoff mengembangkan metode yang efektif untuk menentukan nilai arus dalam suatu rangkaian listrik, menggunakan metode dan konsep yang kemudian mendapat hak kewarganegaraan dalam teori graf. 10 tahun kemudian, ahli matematika Inggris A. Keli (ibunya orang Rusia, dia berbicara bahasa Rusia dan mengikuti literatur matematika Rusia; dia termasuk di antara sedikit ahli matematika yang sejak awal memahami dan mendukung gagasan N.I. Lobachevsky) mengembangkan teori pohon untuk menghitung jumlah isomer hidrokarbon jenuh dengan jumlah tertentu N atom karbon.

Dalam matematika, graf adalah kumpulan titik-titik berhingga yang disebut simpul; yang mana di antara mereka dihubungkan satu sama lain oleh garis yang disebut tepi grafik.

Grafik adalah sekumpulan titik-titik yang digambarkan pada suatu bidang (lembar kertas, papan), yang beberapa pasangnya dihubungkan oleh garis. Titik-titik tersebut disebut simpul pada suatu graf, dan garis-garisnya disebut sisi. Derajat suatu simpul adalah banyaknya sisi yang muncul dari simpul tersebut.

Saat melihat peta geografis, jaringan kereta api langsung menarik perhatian Anda. Ini adalah grafik tipikal: lingkaran mewakili stasiun yang merupakan simpul dari grafik, dan jalur yang menghubungkannya mewakili sisi-sisinya.

Gambar 3

Grafik pada Gambar 3 menggambarkan diagram jalan antara desa M, A, B, C dan D. Di sini, setiap dua simpul dihubungkan oleh sebuah sisi. Grafik seperti ini disebut lengkap. Angka-angka pada gambar menunjukkan jarak antar desa di sepanjang jalan tersebut. Biarlah ada kantor pos di desa M dan tukang pos harus mengantarkan surat ke empat desa lainnya. Ada banyak rute perjalanan yang berbeda. Bagaimana cara memilih yang terpendek? Cara termudah adalah dengan menganalisis semua opsi. Grafik baru akan membantu Anda melakukan hal ini, sehingga memudahkan untuk melihat kemungkinan rute. Puncak M di atas adalah awal rute. Dari sana Anda dapat memulai perjalanan dengan empat cara berbeda: ke A, ke B, ke C atau ke D. Setelah mengunjungi salah satu desa, ada tiga pilihan untuk melanjutkan rute, lalu dua, lalu jalan menuju desa terakhir dan lagi ke M. Total 43 21  24 cara.

Masalah serupa sering muncul ketika mencari pilihan terbaik untuk mendistribusikan barang ke toko dan material ke lokasi konstruksi.

Pertimbangkan salah satu masalah paling sederhana: “Pensil merah, biru, kuning dan hijau ada dalam empat kotak, satu per satu. Warna pensilnya berbeda dengan warna kotaknya. Diketahui pensil hijau berada di dalam kotak biru, tetapi pensil merah tidak berada di kotak kuning. Di kotak mana setiap pensil dimasukkan?”

Mari kita tunjukkan pensil dan kotak dengan titik. Garis padat akan menunjukkan bahwa pensil ada di dalam kotak yang sesuai, dan garis putus-putus akan menunjukkan bahwa pensil tidak ada. Kemudian, dengan mempertimbangkan masalahnya, kita punya G 1 (Gbr. Gambar 4).

Gambar 4

Selanjutnya, kita lengkapi grafiknya sesuai dengan aturan berikut: karena tepat satu pensil dapat terletak di dalam kotak, maka satu garis padat dan tiga garis putus-putus harus keluar dari setiap titik. Hasilnya adalah grafik G 2 , yang memberikan solusi untuk masalah tersebut.

Ketika memecahkan masalah yang biasa disebut logis dalam sains populer dan literatur metodologis, sebagai suatu peraturan, mereka tidak terlalu bergantung pada pengetahuan dan keterampilan sekolah. Dalam hal ini, mereka secara tradisional dianggap sebagai ukuran kecerdikan, indikator tingkat kemampuan matematika, ketajaman berpikir, kemampuan menggunakan memori, dan sering dibahas di klub matematika sekolah.

Memecahkan banyak masalah logika dengan menggunakan grafik cukup mudah diakses oleh siswa yang lebih muda. Untuk melakukan ini, mereka hanya perlu memiliki pemahaman intuitif tentang grafik dan sifat-sifatnya yang paling jelas.

Mari kita lihat contoh penggunaan grafik untuk menyelesaikan beberapa masalah umum. Dalam hal ini, kita akan merepresentasikan objek berdasarkan titik, dan hubungan di antara objek tersebut – berdasarkan segmen (posisi titik dan panjang segmen dapat berubah-ubah).

Klarifikasi struktur masalah logis dari sudut pandang metode solusi yang diterapkan memungkinkan untuk mengisolasi kelas-kelas tertentu dari masalah tersebut.

Tugas 1. Tiga orang teman sedang berbicara: Belokurov, Chernov dan Ryzhov. Si rambut coklat berkata kepada Belokurov: “Sangat mengherankan bahwa salah satu dari kami berambut pirang, yang lain berambut coklat, yang ketiga berambut merah, tapi tidak ada warna rambut yang cocok dengan nama keluarga mereka.” Apa warna rambut yang dimiliki masing-masing temanmu?

Mari kita berikan solusi detailnya. Mari kita buat grafik hubungan yang ditentukan dalam rumusan masalah. Untuk melakukan ini, pertama-tama, mari kita soroti banyak nama keluarga M dan banyak warna rambut KE, unsur-unsurnya akan dilambangkan dengan titik. Tetapkan poin M sebut saja dengan huruf B, Ch, R (Belokurov, Chernov dan Ryzhov); poin set kedua - b, br, p (pirang, berambut cokelat, merah). Jika suatu titik dari suatu himpunan bersesuaian dengan suatu titik dari himpunan lainnya, kita akan menghubungkannya dengan garis padat, dan jika tidak bersesuaian, kita akan menghubungkannya dengan garis putus-putus. Kondisi permasalahan hanya menunjukkan ketidakkonsistenan, sehingga terlebih dahulu akan muncul grafik seperti pada Gambar 5.

Gambar 5

Dari kondisi soal dapat disimpulkan bahwa untuk setiap titik dari himpunan M hanya ada satu tonka dari sekian banyak tonka KE, yang sesuai dengan yang pertama dan, sebaliknya, dengan setiap titik dari himpunan KE sesuai dengan satu dan hanya satu titik dari himpunan M. Tugasnya adalah menemukan satu-satunya korespondensi yang mungkin antara elemen-elemen himpunan M Dan KE, yaitu, untuk menemukan tiga garis padat yang menghubungkan titik-titik yang bersesuaian dari himpunan.

Prinsip pemecahan masalah itu sederhana. Jika suatu titik dihubungkan ke dua titik himpunan lain dengan garis putus-putus, maka titik tersebut harus dihubungkan ke titik ketiganya dengan garis padat. Oleh karena itu, grafik pada Gambar 5 dilengkapi dengan garis padat yang menghubungkan titik B dan p, P dan b (Gambar 6).

Gambar 7

Jadi, pada grafik gambar ini kita otomatis membaca jawabannya: Belokurov berambut merah, Chernov berambut pirang, Ryzhov berambut coklat. Teknik yang sama dapat digunakan untuk menyelesaikan, misalnya soal 2 dan 3.

Tugas 2. Pai dipanggang untuk Vanya, Kolya, dan Misha: satu dengan kubis, satu lagi dengan nasi, yang ketiga dengan apel. Misha tidak suka pai apel dan tidak memakannya dengan kubis. Vanya tidak suka pai kubis. Siapa yang makan pai apa?

Tugas 3. Tiga orang teman bekerja di pabrik yang sama: seorang mekanik, seorang tukang bubut dan seorang tukang las. Nama belakang mereka adalah Borisov, Ivanov dan Semenov. Tukang kunci tidak mempunyai saudara laki-laki atau perempuan, dia adalah anak bungsu dari temannya. Semenov, menikah dengan saudara perempuan Borisov, lebih tua dari turner. Siapa nama mekanik, tukang bubut dan tukang las?

Masalah di atas dapat diselesaikan dengan sukses menggunakan tabel. Metode ini atau modifikasinya direkomendasikan dan dibahas dalam banyak buku sains dan alat bantu pengajaran populer. Namun, dimungkinkan untuk menunjukkan kelas-kelas permasalahan yang mana penggunaan grafik yang diwakili oleh titik dan segmen ternyata lebih mudah dan dapat dibenarkan. Penggunaan metode tabel seperti tabel turnamen atau generalisasinya dalam pengambilan keputusan memaksa bagian penting dari penalaran dilakukan “secara lisan”. Pada saat yang sama, Anda harus berulang kali kembali ke kondisi masalah, ke hasil antara, mengingat banyak hal dan menggunakan informasi yang diterima pada waktu yang tepat. Jenis permasalahan ini mencakup permasalahan dengan tiga atau lebih kumpulan objek yang sedang dipertimbangkan.

Tugas 4. Tiga kawan - Ivan, Dmitry dan Stepan - mengajar berbagai mata pelajaran (kimia, biologi, fisika) di sekolah-sekolah di Moskow, Leningrad dan Kyiv. Diketahui:

1. Ivan tidak bekerja di Moskow, dan Dmitry tidak bekerja di Leningrad;

2. Moskvich tidak mengajarkan fisika;

3. Orang yang bekerja di Leningrad mengajar kimia;

4. Dmitry tidak mengajar biologi.

Mata pelajaran apa dan di kota apa yang diajarkan masing-masing kawan?

Larutan. Mari kita bedakan tiga himpunan: himpunan nama, himpunan benda, dan himpunan kota. Sebuah elemen dari masing-masing himpunan pada Gambar 4 diberikan oleh titiknya sendiri (huruf-huruf dalam gambar ini adalah huruf pertama dari kata-kata yang bersesuaian). Jika dua titik dari himpunan berbeda mencirikan karakteristik orang yang berbeda, maka kita akan menghubungkan titik-titik tersebut dengan garis putus-putus. Jika dua titik dari himpunan berbeda sesuai dengan karakteristik satu orang, maka kita akan menghubungkan titik-titik tersebut berpasangan dengan garis padat. Penting bahwa, sesuai dengan kondisi soal, untuk setiap titik dari himpunan mana pun di setiap himpunan lainnya hanya ada satu dan hanya satu titik yang bersesuaian dengannya.

Angka 8

Jadi, grafik pada Gambar 8 memuat semua elemen himpunan yang ditentukan dalam kondisi dan hubungan di antara elemen-elemen tersebut. Masalah dalam bahasa graf adalah menemukan tiga segitiga “padat” dengan simpul-simpul dalam himpunan berbeda.

Mari kita perhatikan grafik pada Gambar 8. Segmen putus-putus XD menunjukkan dirinya sendiri Memang, A berkorespondensi dengan X dan, pada saat yang sama, A tidak berkorespondensi dengan D, yaitu X tidak dapat berkorespondensi dengan D. Jadi, operasi grafik tipikal untuk ini Jenis soal yang digunakan: jika segitiga dengan titik sudut pada tiga himpunan berbeda, satu sisi padat, sisi kedua putus-putus, maka sisi ketiga harus putus-putus. Dari kondisi soal dapat disimpulkan bahwa operasi lain pada grafik tersebut seragam: jika suatu titik dihubungkan oleh segmen putus-putus ke dua titik pada himpunan kedua, maka titik tersebut harus dihubungkan ke titik ketiga dari himpunan ini dengan segmen padat. Ini adalah bagaimana segmen DF yang berkesinambungan digambar. Selanjutnya gambarlah ruas putus-putus DM (pada segitiga DFM sisi DF padat, dan FM putus-putus), DK padat (DM dan DL putus-putus), Sekarang kita hubungkan titik F dan K dengan ruas padat. Jika dalam sebuah segitiga dengan titik sudut pada himpunan berbeda, dua sisinya padat, maka sisi ketiganya juga padat. Segitiga “padat” pertama DFK telah ditemukan. Jadi, tanpa kembali ke teks soal, hanya dipandu oleh operasi alami pada grafik yang dijelaskan di atas, kita menemukan solusinya (Gbr. 9).

Gambar 9

Mari kita perhatikan urutan pelaksanaan segmen: HD, DF, DM, DK, FC, MS, IL, CI, BM, BS. Titik sudut dari masing-masing segitiga “padat” yang dihasilkan menentukan jawaban dari soal: Ivan mengajar kimia di Leningrad, Dmitry mengajar fisika di Kyiv, dan Stepan mengajar biologi di Moskow.

Dalam soal berikut, penggunaan grafik membantu mendeteksi keberadaan dua solusi.

Tugas 5. Masha, Lida, Zhenya, dan Katya dapat memainkan alat musik yang berbeda (cello, piano, gitar, dan biola), tetapi masing-masing hanya dapat memainkan satu alat musik. Mereka juga berbicara bahasa asing yang berbeda (Inggris, Prancis, Jerman, dan Spanyol), tetapi masing-masing hanya dapat menggunakan satu alat musik. . Yang diketahui :

1. gadis yang bermain gitar berbicara bahasa Spanyol;

2. Lida tidak bisa bermain biola atau cello dan tidak bisa berbahasa Inggris;

3. Masha tidak bermain biola atau cello dan tidak tahu bahasa Inggris;

4. seorang gadis yang berbicara bahasa Jerman tidak memainkan cello;

5. Zhenya tahu bahasa Prancis, tapi tidak bisa bermain biola.

Siapa yang memainkan alat musik apa dan bahasa asing apa yang dia ketahui?

Kondisi masalah sesuai dengan grafik yang ditunjukkan pada Gambar 10.

Gambar 10

Notasi dan prinsip penyelesaian di sini sama seperti pada soal 4. Mari kita menggambar segmen padat berikut secara berurutan: KS, VZH, VF, AK (Gbr. 11).

Gambar 11

Dengan demikian, terbentuklah dua segitiga “padat” ZHVF dan KSA. Kami melakukan segmen kendaraan peluncuran berkelanjutan lainnya. Sekarang kami yakin bahwa kondisi permasalahan tidak menjamin pilihan poin ketiga yang jelas untuk masing-masing pasangan RN dan GI. Opsi berikut untuk segitiga “padat” dimungkinkan: MGI dan OSR atau LGI dan MRN. Jadi, masalahnya memiliki dua solusi.

Mari kita sajikan sebuah masalah di mana grafiknya memungkinkan seseorang dengan mudah mendeteksi redundansi suatu kondisi.

Tugas 6. Enam mitra dari berbagai profesi ikut serta dalam turnamen catur: seorang turner, seorang mekanik, seorang insinyur, seorang guru, seorang dokter dan seorang pengemudi. Diketahui:

1. di babak pertama Andreev bermain dengan dokter, guru dengan Borisov, dan Grigoriev dengan Evdokimov;

2. di babak kedua, Dmitriev bermain dengan turner, dan dokter dengan Borisov;

3. di babak ketiga, Evdokimov bermain dengan seorang insinyur;

4. di akhir turnamen pembagian tempat seperti ini - BorisovSAYAtempat, Grigoriev dan insinyur itu berbagiIIDanAKU AKU AKUtempat, Dmitriev ambilIVtempat, dan Zolotarev serta mekaniknya berbagi tempat kelima dan keenam.

Profesi apa yang dimiliki Grigoriev, Dmitriev, dan Evdokimov?

Teks karya diposting tanpa gambar dan rumus.
Versi lengkap karya ini tersedia di tab "File Kerja" dalam format PDF

PERKENALAN

“Dalam matematika yang harus diingat bukanlah rumusnya, melainkan proses berpikirnya…”

E. I. Ignatiev

Teori graf saat ini merupakan cabang matematika yang berkembang secara intensif. Hal ini dijelaskan oleh fakta bahwa banyak objek dan situasi yang digambarkan dalam bentuk model grafik, yang sangat penting untuk berfungsinya kehidupan sosial secara normal. Faktor inilah yang menentukan relevansi kajian mereka yang lebih rinci. Oleh karena itu, topik karya ini cukup relevan.

Target karya penelitian: mengetahui ciri-ciri penerapan teori graf dalam berbagai bidang ilmu dan dalam memecahkan masalah logika.

Tujuannya mengidentifikasi hal-hal berikut tugas:

mengenal sejarah teori graf;

mempelajari konsep dasar teori graf dan ciri-ciri utama graf;

menunjukkan penerapan praktis teori graf dalam berbagai bidang ilmu;

Pertimbangkan cara untuk memecahkan masalah menggunakan grafik dan buat masalah Anda sendiri.

Sebuah Objek penelitian: bidang aktivitas manusia untuk penerapan metode grafik.

Barang Penelitian: bagian matematika “Teori Grafik”.

Hipotesa. Kami berhipotesis bahwa mempelajari teori grafik dapat membantu siswa memecahkan masalah logika dalam matematika, yang akan membentuk minat masa depan mereka.

Metode pekerjaan penelitian:

Selama penelitian kami, metode berikut digunakan:

1) Bekerja dengan berbagai sumber informasi.

2) Deskripsi, pengumpulan, sistematisasi materi.

3) Observasi, analisis dan perbandingan.

4) Persiapan tugas.

Signifikansi teoritis dan praktis Karya ini ditentukan oleh fakta bahwa hasilnya dapat digunakan dalam ilmu komputer, matematika, geometri, menggambar dan pengajaran di kelas, serta untuk berbagai pembaca yang tertarik dengan topik ini. Karya penelitian ini memiliki orientasi praktis yang jelas, karena dalam karyanya penulis menyajikan banyak contoh penggunaan grafik dalam berbagai bidang ilmu pengetahuan, dan menyusun tugasnya sendiri. Materi ini dapat digunakan pada kelas matematika pilihan.

BAB I. TINJAUAN TEORITIS MATERI PADA TOPIK PENELITIAN

Dalam matematika, “grafik” dapat digambarkan sebagai gambar yang mewakili sejumlah titik yang dihubungkan oleh garis. "Hitungan" berasal dari kata Latin "graphio" - saya menulis, seperti gelar bangsawan yang terkenal.

Dalam matematika, definisi grafik diberikan sebagai berikut:

Istilah "grafik" dalam matematika didefinisikan sebagai berikut:

Grafik - ini adalah himpunan titik yang terbatas - puncak, yang dapat dihubungkan dengan garis - Tulang iga .

Contoh grafik meliputi gambar poligon, rangkaian listrik, representasi skema maskapai penerbangan, kereta bawah tanah, jalan raya, dll. Pohon keluarga juga merupakan graf yang simpul-simpulnya merupakan anggota marga, dan ikatan kekerabatan berperan sebagai tepi graf tersebut.

Beras. 1 Contoh Grafik

Banyaknya sisi yang dimiliki oleh satu titik disebut derajat simpul graf . Jika derajat suatu simpul ganjil, maka simpul tersebut disebut - aneh . Jika derajat suatu titik genap, maka titik tersebut disebut bahkan.

Beras. 2 titik puncak grafik

Grafik nol adalah graf yang hanya terdiri dari simpul-simpul terisolasi yang tidak dihubungkan oleh sisi-sisinya.

Grafik lengkap adalah graf yang setiap pasang simpulnya dihubungkan oleh sebuah sisi. N-gon, yang semua diagonalnya digambar, dapat menjadi contoh grafik lengkap.

Jika Anda memilih jalur dalam grafik yang titik awal dan titik akhirnya bertepatan, maka jalur seperti itu disebut siklus grafik . Jika setiap titik pada suatu graf dilewati paling banyak satu kali, maka siklus ditelepon sederhana .

Jika setiap dua simpul pada suatu graf dihubungkan oleh sebuah sisi, maka ini adalah terhubung grafik. Grafiknya disebut tidak berhubungan , jika berisi setidaknya satu pasang simpul yang tidak terhubung.

Jika suatu graf terhubung tetapi tidak mengandung siklus, maka graf tersebut disebut pohon .

Jalan Penghitungan adalah barisan yang setiap dua sisi bertetangga yang mempunyai titik sudut yang sama hanya muncul satu kali.

Panjang rantai simpul terpendek A dan b dipanggil jarak antara puncak A dan B.

Puncak A ditelepon tengah grafik, jika jarak antara simpul A dan simpul lainnya adalah simpul terkecil yang mungkin ada. Ada jarak yang begitu jauh radius grafik.

Jarak maksimum yang mungkin terjadi antara dua titik pada suatu graf disebut diameter grafik.

Pewarnaan grafik dan penerapannya.

Jika Anda melihat lebih dekat pada peta geografis, Anda dapat melihat jalur kereta api atau jalan raya, yang berupa grafik. Selain itu, pada peta terdapat grafik yang berisi batas antar negara (kabupaten, wilayah).

Pada tahun 1852, pelajar bahasa Inggris Francis Guthrie diberi tugas mewarnai peta Inggris Raya, menyorot setiap daerah dengan warna berbeda. Karena sedikitnya pilihan cat, Guthrie menggunakannya kembali. Dia memilih warna-warna tersebut sehingga negara-negara yang memiliki bagian perbatasan yang sama dapat dicat dengan warna yang berbeda. Timbul pertanyaan berapa jumlah minimum cat yang dibutuhkan untuk mewarnai berbagai peta. Francis Guthrie menyarankan, meskipun dia tidak dapat membuktikan, bahwa empat warna saja sudah cukup. Masalah ini sempat hangat diperbincangkan di kalangan mahasiswa, namun kemudian terlupakan.

"Masalah empat warna" membangkitkan minat yang semakin besar, namun tidak pernah terpecahkan, bahkan oleh ahli matematika terkemuka. Pada tahun 1890, matematikawan Inggris Percy Heawood membuktikan bahwa lima warna cukup untuk mewarnai peta apa pun. Baru pada tahun 1968 mereka mampu membuktikan bahwa 4 warna cukup untuk mewarnai peta yang menggambarkan kurang dari empat puluh negara.

Pada tahun 1976, masalah ini diselesaikan dengan menggunakan komputer oleh dua ahli matematika Amerika, Kenneth Appel dan Wolfgangt Haken. Untuk mengatasinya, semua kartu dibagi menjadi 2000 jenis. Sebuah program komputer diciptakan yang memeriksa semua jenis kartu untuk mengidentifikasi kartu yang empat warnanya tidak cukup untuk diwarnai. Komputer tidak dapat mempelajari hanya tiga jenis peta, sehingga ahli matematika mempelajarinya sendiri. Hasilnya, ditemukan bahwa 4 warna cukup untuk mewarnai seluruh 2000 jenis kartu. Mereka mengumumkan solusi terhadap masalah empat warna. Pada hari ini, kantor pos di universitas tempat Appel dan Haken bekerja membubuhkan stempel pada semua prangko dengan tulisan: “Empat warna sudah cukup.”

Anda dapat membayangkan masalah empat warna dengan sedikit berbeda.

Untuk melakukan ini, pertimbangkan peta sembarang, sajikan dalam bentuk grafik: ibu kota negara bagian adalah simpul dari grafik, dan tepi grafik menghubungkan simpul (ibu kota) yang negara bagiannya memiliki batas yang sama. Untuk memperoleh graf seperti itu dirumuskan masalah sebagai berikut: graf tersebut perlu diwarnai dengan empat warna agar simpul-simpul yang mempunyai sisi yang sama diwarnai dengan warna yang berbeda.

Grafik Euler dan Hamilton

Pada tahun 1859, ahli matematika Inggris William Hamilton merilis sebuah teka-teki - sebuah dodecahedron kayu (dodecahedron), yang dua puluh simpulnya ditandai dengan kancing. Setiap puncak memiliki nama salah satu kota terbesar di dunia - Kanton, Delhi, Brussel, dll. Tugasnya adalah menemukan jalur tertutup yang melewati tepi polihedron, mengunjungi setiap titik hanya sekali. Untuk menandai jalan, digunakan tali yang diikatkan pada paku.

Siklus Hamilton adalah graf yang lintasannya merupakan siklus sederhana yang melewati semua simpul pada graf tersebut satu kali.

Kota Kaliningrad (sebelumnya Koenigsberg) terletak di Sungai Pregel. Sungai itu menyapu dua pulau, yang dihubungkan satu sama lain dan ke tepiannya melalui jembatan. Jembatan-jembatan lama sudah tidak ada lagi. Kenangan mereka hanya tersisa di peta kota.

Suatu hari, seorang penduduk kota bertanya kepada temannya apakah mungkin untuk berjalan melintasi semua jembatan, mengunjungi masing-masing jembatan hanya sekali, dan kembali ke tempat perjalanan dimulai. Masalah ini menarik minat banyak warga kota, namun tidak ada yang bisa menyelesaikannya. Isu ini menarik minat para ilmuwan dari banyak negara. Solusi dari masalah tersebut diperoleh oleh ahli matematika Leonhard Euler. Selain itu, ia merumuskan pendekatan umum untuk memecahkan masalah tersebut. Untuk melakukan hal ini, ia mengubah peta menjadi grafik. Simpul dari graf ini adalah tanah, dan ujung-ujungnya adalah jembatan yang menghubungkannya.

Saat menyelesaikan masalah jembatan Königsberg, Euler berhasil merumuskan sifat-sifat grafik.

Suatu graf dapat digambar dengan memulai dari satu simpul dan berakhir pada simpul yang sama dengan satu goresan (tanpa menggambar sepanjang garis yang sama sebanyak dua kali dan tanpa mengangkat pensil dari kertas) jika semua simpul pada graf tersebut genap.

Jika terdapat suatu graf yang mempunyai dua simpul ganjil, maka simpul-simpul tersebut juga dapat dihubungkan dengan satu guratan. Untuk melakukan ini, Anda harus memulai dari satu dan menyelesaikan di titik ganjil mana pun yang lain.

Jika terdapat graf yang mempunyai lebih dari dua simpul ganjil, maka graf tersebut tidak dapat digambar dengan satu guratan.

Jika kita menerapkan sifat-sifat ini pada masalah jembatan, kita dapat melihat bahwa semua simpul pada graf yang diteliti adalah ganjil, artinya graf tersebut tidak dapat dihubungkan dengan satu garis, yaitu. Tidak mungkin untuk melintasi semua jembatan satu kali dan mengakhiri perjalanan di tempat dimulainya.

Jika suatu graf mempunyai suatu siklus (tidak harus sederhana) yang memuat semua sisi graf tersebut satu kali, maka siklus tersebut disebut Siklus Euler . Rantai Euler (jalur, siklus, kontur) adalah rantai (jalur, siklus, kontur) yang memuat semua sisi (busur) dari graf satu kali.

BAB II. DESKRIPSI STUDI DAN HASILNYA

2.1. Tahapan penelitian

Untuk menguji hipotesis, penelitian ini meliputi tiga tahap (Tabel 1):

Tahapan penelitian

Tabel 1.

		Metode yang digunakan
Studi teoritis tentang masalah tersebut	Pelajari dan analisis literatur pendidikan dan ilmiah.	- berpikir mandiri;  studi sumber informasi; - mencari literatur yang diperlukan.
Penelitian praktis tentang masalah tersebut	Pertimbangkan dan analisis bidang penerapan praktis grafik;	- observasi; - analisis; - perbandingan; - survei.
Tahap 3. Penggunaan praktis dari hasilnya	Meringkas informasi yang dipelajari;	- sistematisasi;  laporan (lisan, tertulis, dengan demonstrasi materi)	September 2017

2.2. Area penerapan praktis grafik

Grafik dan informasi

Teori informasi banyak memanfaatkan sifat-sifat pohon biner.

Misalnya, jika Anda perlu menyandikan sejumlah pesan tertentu dalam bentuk urutan angka nol dan angka tertentu dengan panjang yang berbeda-beda. Suatu kode dianggap terbaik untuk probabilitas kata kode tertentu jika rata-rata panjang kata adalah yang terkecil dibandingkan dengan distribusi probabilitas lainnya. Untuk mengatasi masalah ini, Huffman mengusulkan suatu algoritma di mana kode direpresentasikan sebagai grafik pohon dalam kerangka teori pencarian. Untuk setiap titik, sebuah pertanyaan diajukan, jawabannya dapat berupa "ya" atau "tidak" - yang sesuai dengan dua sisi yang keluar dari titik tersebut. Pembangunan pohon seperti itu selesai setelah ditetapkan apa yang diperlukan. Hal ini dapat digunakan dalam mewawancarai beberapa orang, ketika jawaban pertanyaan sebelumnya tidak diketahui sebelumnya, rencana wawancara direpresentasikan sebagai pohon biner.

Grafik dan kimia

A. Cayley juga mempertimbangkan masalah kemungkinan struktur hidrokarbon jenuh (atau jenuh), yang molekulnya diberikan dengan rumus:

CnH 2n+2

Semua atom hidrokarbon bervalensi 4, semua atom hidrogen bervalensi 1. Rumus struktur hidrokarbon paling sederhana ditunjukkan pada gambar.

Setiap molekul hidrokarbon jenuh dapat direpresentasikan sebagai pohon. Ketika semua atom hidrogen dihilangkan, atom hidrokarbon yang tersisa membentuk pohon dengan simpul yang derajatnya tidak lebih dari empat. Artinya jumlah kemungkinan struktur yang diinginkan (homolog suatu zat tertentu) sama dengan jumlah pohon yang derajat puncaknya tidak lebih dari 4. Masalah ini direduksi menjadi masalah pencacahan pohon dari jenis tertentu. D. Polya mempertimbangkan masalah ini dan generalisasinya.

Grafik dan biologi

Proses reproduksi bakteri merupakan salah satu jenis proses percabangan yang terdapat dalam teori biologi. Biarkan setiap bakteri, setelah waktu tertentu, mati atau membelah menjadi dua. Oleh karena itu, untuk satu bakteri kita memperoleh pohon biner dari reproduksi keturunannya. Pertanyaan permasalahannya adalah sebagai berikut: berapa banyak kasus yang dikandungnya? k keturunan generasi ke-n dari satu bakteri? Hubungan dalam biologi ini disebut proses Galton-Watson, yang menunjukkan jumlah kasus yang diperlukan.

Grafik dan Fisika

Tugas yang sulit dan membosankan bagi setiap amatir radio adalah membuat sirkuit tercetak (sepiring bahan isolasi dielektrik dan trek tergores dalam bentuk strip logam). Persimpangan lintasan hanya terjadi pada titik-titik tertentu (lokasi trioda, resistor, dioda, dll) menurut aturan tertentu. Akibatnya, ilmuwan dihadapkan pada tugas menggambar grafik datar dengan simpul di dalamnya

Jadi, semua hal di atas menegaskan nilai praktis grafik.

matematika internet

Internet adalah sistem jaringan komputer yang saling berhubungan di seluruh dunia untuk menyimpan dan mengirimkan informasi.

Internet dapat direpresentasikan sebagai sebuah graf, dimana simpul-simpul dari graf tersebut adalah situs-situs Internet, dan ujung-ujungnya adalah tautan (hyperlink) yang berpindah dari satu situs ke situs lainnya.

Grafik web (Internet), yang memiliki milyaran simpul dan tepi, terus berubah - situs secara spontan ditambahkan dan dihilangkan, tautan menghilang dan ditambahkan. Namun, Internet memiliki struktur matematis, mematuhi teori grafik, dan memiliki beberapa sifat “stabil”.

Grafik webnya jarang. Ini hanya berisi tepi beberapa kali lebih banyak daripada simpul.

Meskipun jarang, Internet sangat ramai. Anda dapat berpindah dari satu situs ke situs lain menggunakan tautan dalam 5 - 6 klik (teori terkenal "enam jabat tangan").

Seperti yang kita ketahui, derajat suatu graf adalah jumlah sisi yang dimiliki suatu titik. Derajat simpul pada grafik web didistribusikan menurut hukum tertentu: proporsi situs (simpul) dengan banyak tautan (tepi) adalah kecil, dan proporsi situs dengan jumlah tautan kecil adalah besar. Secara matematis dapat ditulis seperti ini:

di mana adalah proporsi simpul dengan derajat tertentu, adalah derajat suatu simpul, adalah konstanta yang tidak bergantung pada jumlah simpul pada grafik web, yaitu tidak berubah selama proses penambahan atau penghapusan situs (simpul).

Hukum kekuasaan ini bersifat universal untuk jaringan yang kompleks - dari biologis hingga antar bank.

Internet secara keseluruhan tahan terhadap serangan acak terhadap situs.

Karena penghancuran dan pembuatan situs terjadi secara independen dan dengan probabilitas yang sama, grafik web, dengan probabilitas mendekati 1, mempertahankan integritasnya dan tidak dimusnahkan.

Untuk mempelajari Internet, perlu dibangun model grafik acak. Model ini harus memiliki sifat Internet yang sebenarnya dan tidak terlalu rumit.

Masalah ini belum terselesaikan sepenuhnya! Memecahkan masalah ini - membangun model Internet berkualitas tinggi - akan memungkinkan kita mengembangkan alat baru untuk meningkatkan pencarian informasi, mengidentifikasi spam, dan menyebarkan informasi.

Konstruksi model biologis dan ekonomi dimulai jauh lebih awal daripada tugas membangun model matematika Internet. Namun, kemajuan dalam pengembangan dan studi Internet telah memungkinkan untuk menjawab banyak pertanyaan mengenai semua model ini.

Matematika internet diminati oleh banyak spesialis: ahli biologi (memprediksi pertumbuhan populasi bakteri), pemodal (risiko krisis), dll. Studi tentang sistem tersebut adalah salah satu cabang utama matematika terapan dan ilmu komputer.

Murmansk menggunakan grafik.

Ketika seseorang tiba di kota baru, biasanya keinginan pertama adalah mengunjungi tempat-tempat wisata utama. Namun pada saat yang sama, jumlah waktunya seringkali terbatas, dan dalam kasus perjalanan bisnis, sangat sedikit. Oleh karena itu, perlu merencanakan tamasya Anda terlebih dahulu. Dan grafik akan sangat membantu dalam membangun rute Anda!

Sebagai contoh, perhatikan kasus umum saat tiba di Murmansk dari bandara untuk pertama kalinya. Kami berencana untuk mengunjungi objek wisata berikut:

1. Gereja Ortodoks Laut Juru Selamat di Atas Air;

2. Katedral St.Nicholas;

3. Oseanarium;

4. Monumen kucing Semyon;

5. Pemecah es nuklir Lenin;

6. Lampu Taman Murmansk;

7. Taman Lembah Kenyamanan;

8. Jembatan Kola;

9. Museum Sejarah Perusahaan Pelayaran Murmansk;

10. Persegi Lima Sudut;

11. Pelabuhan perdagangan laut

Pertama, mari kita cari lokasi tempat-tempat ini di peta dan dapatkan representasi visual dari lokasi dan jarak antar objek wisata. Jaringan jalan raya cukup berkembang, dan perjalanan dengan mobil tidak akan sulit.

Atraksi pada peta (di sebelah kiri) dan grafik yang dihasilkan (di sebelah kanan) ditunjukkan pada gambar yang sesuai pada LAMPIRAN No.1. Dengan demikian, pendatang baru pertama-tama akan lewat di dekat Jembatan Kola (dan jika diinginkan, dapat melintasinya bolak-balik); kemudian dia akan bersantai di Taman Cahaya Murmansk dan Lembah Kenyamanan dan melanjutkan perjalanan. Hasilnya, rute optimal adalah:

Dengan menggunakan grafik, Anda juga dapat memvisualisasikan skema pelaksanaan jajak pendapat. Contohnya disajikan pada LAMPIRAN No.2. Tergantung pada jawaban yang diberikan, responden ditanyai pertanyaan yang berbeda. Misalnya, jika dalam survei sosiologi No. 1 responden menganggap matematika sebagai ilmu yang paling penting, ia akan ditanya apakah ia merasa percaya diri dalam pelajaran fisika; jika dia berpikir sebaliknya, pertanyaan kedua adalah mengenai tuntutan terhadap bidang humaniora. Simpul dari graf tersebut adalah pertanyaan, dan sisinya adalah pilihan jawaban.

2.3. Penerapan teori graf untuk pemecahan masalah

Teori graf digunakan untuk memecahkan masalah dari berbagai mata pelajaran: matematika, biologi, ilmu komputer. Kami mempelajari prinsip pemecahan masalah menggunakan teori graf dan menciptakan masalah kami sendiri pada topik penelitian.

Tugas No.1.

Lima teman sekelas berjabat tangan di reuni sekolah menengah. Berapa banyak jabat tangan yang dilakukan?

Solusi: Mari kita nyatakan teman sekelas dengan simpul dari grafik. Mari kita hubungkan setiap simpul dengan garis ke empat simpul lainnya. Kami mendapatkan 10 baris, ini adalah jabat tangan.

Jawaban: 10 jabat tangan (setiap baris berarti satu jabat tangan).

Tugas No.2.

Di desa nenek saya, dekat rumahnya, tumbuh 8 pohon: poplar, oak, maple, pohon apel, larch, birch, rowan, dan pinus. Rowan lebih tinggi dari larch, pohon apel lebih tinggi dari maple, oak lebih rendah dari birch, tetapi lebih tinggi dari pinus, pinus lebih tinggi dari rowan, birch lebih rendah dari poplar, dan larch lebih tinggi dari pohon apel. Bagaimana urutan ketinggian pohon dari yang tertinggi ke terpendek?

Larutan:

Pohon adalah simpul dari grafik. Mari kita nyatakan dengan huruf pertama dalam lingkaran. Mari kita menggambar anak panah dari pohon yang rendah ke pohon yang lebih tinggi. Konon abu gunung lebih tinggi dari larch, lalu kita pasang panah dari larch ke abu gunung, pohon birch lebih rendah dari pohon poplar, lalu kita pasang panah dari pohon poplar ke pohon birch, dan seterusnya. Kita mendapatkan grafik dimana kita dapat melihat bahwa pohon terpendek adalah maple, kemudian apel, larch, rowan, pinus, oak, birch dan poplar.

Jawaban: maple, apel, larch, rowan, pinus, oak, birch, dan poplar.

Tugas No.3.

Ibu punya 2 amplop: biasa dan udara, dan 3 perangko: persegi, persegi panjang, dan segitiga. Ada berapa cara Ibu memilih amplop dan prangko untuk mengirim surat kepada Ayah?

Jawaban: 6 cara

Tugas No.4.

Telah dibangun jalan antara pemukiman A, B, C, D, E. Anda perlu menentukan panjang jalur terpendek antara titik A dan E. Anda hanya dapat bergerak di sepanjang jalan yang panjangnya ditunjukkan pada gambar.

Tugas No.5.

Tiga teman sekelas - Maxim, Kirill dan Vova memutuskan untuk terjun dalam olahraga dan lolos seleksi bagian olahraga. Diketahui bahwa 1 anak laki-laki melamar bagian bola basket, dan tiga orang ingin bermain hoki. Maxim hanya mengikuti audisi untuk bagian 1, Kirill terpilih untuk ketiga bagian, dan Vova terpilih untuk bagian 2. Siapa di antara anak laki-laki yang terpilih untuk bagian olahraga yang mana?

Solusi: Untuk menyelesaikan masalah kita akan menggunakan grafik

Pepatah Bola Basket

Kirill Sepak Bola

Hoki Vova

Sejak sampai bola basket hanya satu anak panah yang melesat, lalu Kirill terpilih ke bagian tersebut bola basket. Maka Kirill tidak akan bermain hoki, yang artinya masuk hoki bagian dipilih oleh Maxim, yang mengikuti audisi hanya untuk bagian ini, maka Vova akan menjadi pemain sepak bola.

Tugas No.6.

Karena sakitnya beberapa guru, kepala sekolah perlu menyusun sebagian jadwal sekolah untuk setidaknya satu hari, dengan mempertimbangkan keadaan berikut:

1. Guru keselamatan jiwa setuju untuk memberikan pelajaran terakhir saja;

2. Guru geografi dapat memberikan pelajaran kedua atau ketiga;

3. Ahli matematika siap memberikan pelajaran pertama atau kedua saja;

4. Seorang guru fisika dapat memberikan pelajaran pertama, kedua, atau ketiga, tetapi hanya dalam satu kelas.

Jadwal seperti apa yang dapat dibuat oleh kepala sekolah suatu sekolah agar dapat memuaskan seluruh guru?

Solusi: Masalah ini dapat diselesaikan dengan menelusuri semua opsi yang memungkinkan, namun akan lebih mudah jika Anda menggambar grafik.

1. 1) fisika 2. 1) matematika 3. 1) matematika

2) matematika 2) fisika 2) geografi

3) geografi 3) geografi 3) fisika

4) OBZH 4) OBZH 4) OBZH

Kesimpulan

Dalam penelitian ini teori graf dipelajari secara detail, hipotesis terbukti bahwa studi tentang grafik dapat membantu dalam menyelesaikan masalah-masalah logika, selain itu, teori graf dalam berbagai bidang ilmu dipertimbangkan dan 7 masalah disusun.

Penggunaan grafik ketika mengajar siswa bagaimana menemukan solusi suatu masalah memungkinkan siswa untuk meningkatkan keterampilan grafis mereka dan mengkomunikasikan penalaran dalam bahasa khusus dari sekumpulan titik berhingga, beberapa di antaranya dihubungkan oleh garis. Semua ini berkontribusi pada upaya mengajar siswa untuk berpikir.

Efektivitas kegiatan pendidikan dalam mengembangkan pemikiran sangat tergantung pada derajat aktivitas kreatif siswa dalam memecahkan masalah matematika. Oleh karena itu, diperlukan adanya tugas dan latihan matematika yang dapat mengaktifkan aktivitas mental anak sekolah.

Penerapan tugas dan penggunaan unsur teori graf pada kelas pilihan di sekolah justru bertujuan untuk mengaktifkan aktivitas mental siswa. Kami percaya bahwa materi praktis penelitian kami dapat berguna di kelas matematika pilihan.

Dengan demikian, tujuan penelitian telah tercapai, permasalahan telah terpecahkan. Kedepannya, kami berencana untuk terus mempelajari teori graf dan mengembangkan rute kami sendiri, misalnya menggunakan grafik untuk membuat rute tamasya bus sekolah di ZATO Aleksandrovsk ke museum dan tempat-tempat berkesan di Murmansk.

DAFTAR REFERENSI YANG DIGUNAKAN

Berezina L. Yu "Grafik dan penerapannya" - M.: "Pencerahan", 1979

Gardner M. "Kenyamanan matematika", M. "Mir", 1972

Gardner M. "Teka-teki dan hiburan matematika", M. "Mir", 1971

Gorbachev A. “Kumpulan Soal Olimpiade” - M. MTsNMO, 2005

Zykov A. A. Dasar-dasar teori grafik. - M.: “Buku Universitas”, 2004. - P. 664

Kasatkin V. N. “Masalah matematika yang tidak biasa”, Kyiv, “Radianska School”, 1987

Komponen matematika / Editor dan penyusun N.N. Andreev, S.P. Konovalov, N.M. Panyushkin. - M.: Yayasan "Etudes Matematika" 2015 - 151 hal.

Melnikov O. I. “Masalah yang menghibur dalam teori graf”, Mn. "TetraSistem", 2001

Melnikov O.I. Entahlah di negeri yang diperhitungkan: Sebuah manual untuk siswa. Ed. Ketiga, stereotip. M.: KomKniga, 2007. - 160 hal.

Olehnik S. N., Nesterenko Yu. V., Potapov M. K. “Masalah lama yang menghibur”, M. “Science”, 1988

Ore O. “Grafik dan aplikasinya”, M. “Mir”, 1965

Harari F. Teori Graf / Terjemahan dari Bahasa Inggris. dan kata pengantar V.P.Kozyreva. Ed. G.P. Gavrilova. Ed. ke-2. - M.: Redaksi URSS, 2003. - 296 hal.

LAMPIRAN No.1

Menyusun rute optimal untuk mengunjungi tempat-tempat wisata utama

Murmansk menggunakan grafik.

Rute optimalnya adalah:

8. Jembatan Kola6. Lampu Taman Murmansk7. Taman Lembah Kenyamanan2. Katedral St.Nicholas10. Kotak Lima Sudut5. Pemecah es nuklir Lenin9. Museum Sejarah Perusahaan Pelayaran Murmansk11. Pelabuhan perdagangan laut1. Gereja Ortodoks Laut Juru Selamat di Atas Air4. Monumen kucing Semyon3. Oseanarium.

PANDUAN ATRAKSI MURMANSK

LAMPIRAN No.2

Survei sosiologis No.1, 2

Edisi pendidikan

Yuyukin Nikolay Alekseevich

LR tidak. Ditandatangani untuk segel

Uch. Ed. aku.., .

Universitas Teknik Negeri Voronezh

394026 Voronezh, Jalan Moskovsky. 14

DIREKTORI MAGNETIC DISK

Jurusan Matematika Tinggi dan Pemodelan Fisika dan Matematika

DI ATAS. Yuyukin

MATEMATIKA DISKRIT Bagian 1. Unsur-unsur teori graf

tutorial

DI ATAS. Yuyukin

MATEMATIKA DISKRIT Bagian 1. Unsur-unsur teori graf

tutorial

Voronezh 2004

PERKENALAN

Manual ini dapat digunakan dalam mata kuliah “Matematika Diskrit” oleh mahasiswa VSTU yang belajar pada spesialisasi berikut:

090102 – Keamanan komputer;

090105 – Penyediaan keamanan informasi sistem otomatis secara komprehensif;

090106 - Keamanan informasi sistem telekomunikasi.

Disiplin “Matematika Diskrit” menjamin perolehan pengetahuan dan keterampilan sesuai dengan negara, standar pendidikan umum, dan pada saat yang sama mendorong perolehan pendidikan dasar, pembentukan pandangan dunia dan pengembangan pemikiran logis.

Teori graf adalah alat yang efektif untuk memformalkan masalah teknik modern yang berhubungan dengan objek diskrit. Ini digunakan dalam desain sirkuit terpadu dan sirkuit kontrol, studi tentang automata dan sirkuit logika, dalam analisis sistem, kontrol produksi otomatis, dalam pengembangan komputer dan jaringan informasi, dalam desain sirkuit dan desain topologi, dll.

Tutorial ini menguraikan dasar-dasar, metode dasar dan algoritma teori grafik. Di sini kami menyajikan n-grafik dan digraf; isomorfisme; pohon; Grafik Euler; grafik planar; penutup dan set independen; konektivitas yang kuat

V digraf; Analisis grafik rantai Markov; algoritma untuk menemukan jalur terpendek dalam grafik; Masalah pencarian siklus Hamilton

V grafik; masalah penjual keliling; pencacahan grafik dan pemetaan; tugas ekstrim; masalah optimasi; tugas universal; metode cabang dan terikat; dan juga mengembangkan keterampilan praktis dalam menggunakan konsep-konsep di atas.

Tujuan dari mata kuliah ini adalah untuk mengembangkan pengetahuan teoritis, keterampilan dan kemampuan praktis mahasiswa di bidang pemodelan proses dan fenomena dalam ilmu pengetahuan dan teknologi alam.

ke, dengan kemampuan menggunakan simbol matematika untuk menyatakan hubungan kuantitatif dan kualitatif objek yang diperlukan untuk melakukan kegiatan resmi di bidang keamanan informasi pada tingkat profesional yang tinggi.

Tugas-tugas berikut berfungsi untuk mencapai tujuan ini:

mempelajari konsep teori graf seluas-luasnya;

memperoleh keterampilan dalam memecahkan masalah pendidikan dan praktis;

metode optimasi utama;

mengembangkan keterampilan dalam menetapkan dan memecahkan masalah informasi, memodelkan dan menganalisis informasi dengan menggunakan grafik.

Disiplin “Matematika Diskrit” merupakan salah satu disiplin ilmu matematika terapan. Hal ini didasarkan pada pengetahuan yang diperoleh siswa selama mempelajari disiplin ilmu “Aljabar” dan “Logika Matematika dan Teori Algoritma”. Pengetahuan dan keterampilan yang diperoleh dalam pembelajaran disiplin ilmu “Matematika Diskrit” digunakan dalam penelitian ini profesional umum dan disiplin khusus.

1. KONSEP DASAR TEORI GRAFIK.

1.1. Masalah teori graf.

Teori graf adalah salah satu cabang matematika yang mempelajari sistem hubungan antar objek yang berbeda, seperti halnya konsep relasi. Namun, definisi grafik yang independen menyederhanakan penyajian teori dan membuatnya lebih mudah dipahami dan visual.

Masalah pertama teori graf berkaitan dengan pemecahan masalah hiburan dan teka-teki.

Tugas pertama. Masalah jembatan Königsberg diajukan dan diselesaikan oleh Euler pada tahun 1786. Kota ini terletak di tepian dan dua pulau Sungai Pregolya. Pulau-pulau tersebut dihubungkan satu sama lain dan pantainya melalui tujuh jembatan, seperti yang ditunjukkan pada gambar.

Timbul pertanyaan: apakah mungkin meninggalkan rumah dan kembali lagi, melintasi setiap jembatan tepat satu kali?

Tugas kedua. Masalah tiga rumah dan tiga sumur. Ada tiga rumah dan tiga sumur.

Wajib dibuat jalan setapak dari setiap rumah ke setiap sumur agar jalan tersebut tidak berpotongan. Tugasnya adalah

diselesaikan oleh Pontryagin dan secara independen oleh Kuratovsky di

Tugas ketiga. Sekitar empat warna. Warnai setiap peta pada bidang datar dengan empat warna sehingga tidak ada dua area yang berdekatan dicat dengan warna yang sama.

Banyak hasil dari teori graf yang digunakan untuk memecahkan masalah-masalah praktis dalam ilmu pengetahuan dan teknologi. Jadi, pada pertengahan abad ke-19, Kirchhoff menggunakan teori grafik untuk menghitung rangkaian listrik yang kompleks. Namun, sebagai suatu disiplin matematika, teori graf baru terbentuk pada tahun 30-an abad ke-20. Dalam hal ini, grafik dianggap sebagai beberapa objek matematika abstrak. Mereka digunakan dalam analisis dan sintesis sirkuit dan sistem, dalam perencanaan dan manajemen jaringan, riset operasi, pemrograman, pemodelan kehidupan suatu organisme dan bidang lainnya.

1.2. Definisi dasar.

Graf G= (V,E) merupakan himpunan dua himpunan – himpunan simpul tak kosong V dan himpunan pasangan simpul tak berurutan dan tak beraturan E. Berikut ini kita akan membahas grafik berhingga, yaitu. graf dengan himpunan simpul berhingga dan keluarga pasangan berhingga. Pasangan simpul yang tidak berurutan disebut sisi, dan pasangan simpul yang berurutan disebut busur.

Biasanya, grafik direpresentasikan dengan diagram: simpul adalah titik (atau lingkaran), sisi adalah garis dengan konfigurasi sembarang. Sebuah panah juga menunjukkan arahnya pada busur. Perhatikan bahwa ketika menggambarkan grafik, pembawa

Sifat geometris tepi (panjang, kelengkungan), serta posisi relatif simpul pada bidang, sangatlah penting.

Simpul yang tidak termasuk dalam suatu sisi (busur) disebut terisolasi. Titik-titik yang dihubungkan oleh suatu rusuk atau busur disebut bertetangga. Sisi (busur) dan salah satu dari dua simpulnya disebut insiden.

Mereka mengatakan bahwa sebuah sisi (u,v) menghubungkan simpul-simpul u dan v, dan sebuah busur (u,v) dimulai dari simpul u dan berakhir di simpul v, dengan u disebut awal dan v sebagai akhir busur ini.

Sepasang simpul dapat dihubungkan oleh dua sisi atau lebih (busur searah). Tepi (busur) seperti itu disebut kelipatan. Busur (atau tepi) dapat dimulai atau diakhiri pada titik sudut yang sama. Busur (tepi) seperti itu disebut loop. Graf yang mengandung loop disebut graf semu. Graf yang mempunyai banyak sisi (busur) disebut multigraf.

Graf yang tidak memiliki loop atau banyak sisi disebut graf sederhana. Suatu graf sederhana disebut graf lengkap jika pada setiap pasangan simpulnya terdapat sisi (busur) yang menghubungkan simpul-simpul tersebut. Graf lengkap dengan n simpul dilambangkan dengan K n. Misalnya, ini adalah grafik

Graf yang terdiri dari satu titik terisolasi (K 1) disebut sepele.

Komplemen graf G adalah graf G yang mempunyai simpul-simpul yang sama dengan graf G dan memuat sisi-sisi yang perlu dijumlahkan pada graf G untuk memperoleh graf lengkap.

Untuk setiap non-digrafer cocok secara kanonik graf berarah dengan himpunan simpul yang sama, yang setiap sisinya digantikan oleh dua busur yang bersisian pada simpul yang sama dan mempunyai arah yang berlawanan.

1.3. Derajat simpul grafik.

Derajat (valensi) (notasi d (v) atau derajat (v)) suatu titik v pada graf sederhana G adalah jumlah sisi atau busur yang bersisian dengan titik v tertentu. Saat menghitung valensi simpul pada pseudograf, setiap loop harus dihitung dua kali.

Jika derajat semua simpul pada suatu n-graf sama dengan k, maka graf tersebut disebut reguler (seragam) derajat k. Jika derajat suatu titik adalah 0, maka titik tersebut terisolasi. Jika derajat suatu simpul adalah 1, maka simpul tersebut disebut simpul terminal (menggantung, buntu).

Untuk suatu digraf, banyaknya busur yang berasal dari titik v disebut

bervariasi hasil semi-derajat				(v), dan yang masuk – semi-langkah-

panggilan baru d			(v), Dalam hal ini relasi d (v)=

	(v)+	(v).

Teorema Euler: Jumlah derajat simpul-simpul suatu graf adalah

menggandakan jumlah tulang rusuk, mis.

d(vi)



			(v)

Dimana n adalah jumlah simpul; m – nomor

tulang rusuk (lengkungan). Pernyataan ini dibuktikan dengan fakta bahwa ketika menghitung jumlah derajat simpul, setiap sisi diperhitungkan dua kali - untuk satu ujung tepi dan untuk ujung lainnya.

1.4. Grafik isomorfisme.

Suatu graf disebut berlabel (atau diberi nomor ulang) jika simpul-simpulnya berbeda satu sama lain dalam beberapa hal.

label (angka). Hitungannya dipertimbangkan sepenuhnya diberikan dalam arti sempit, jika penomoran simpul dan sisinya tetap. Dalam hal ini, graf G 1 dan G 2 disebut sama (sebutan G 1 = G 2), jika himpunan simpul dan sisinya berimpit. Dua graf atau pseudograf G 1 = (V 1 ,E 1 ) dan G 2 = (V 2 ,E 2 ) disebut

	isomorfik (notasi G	jika mereka ada

	pemetaan satu-ke-satu: 1)	: V 1 V 2
: E 1 E 2 sedemikian rupa sehingga untuk dua simpul mana pun u, v pada grafik
	relasi ((u, v)) ((u), (v)) valid.

	Dua graf sederhana (tanpa loop dan banyak sisi) G 1		dan G2