Sebelum Anda mulai mempelajari algoritme itu sendiri, Anda perlu memiliki pengetahuan dasar tentang grafik itu sendiri dan memahami cara representasinya di komputer. Semua aspek teori graf tidak akan dijelaskan secara rinci di sini (ini tidak wajib), tetapi hanya aspek-aspek tersebut, ketidaktahuan akan secara signifikan mempersulit asimilasi bidang pemrograman ini.

Beberapa contoh akan memberikan sedikit sketsa grafiknya. Jadi grafik umumnya adalah peta metro atau rute lainnya. Secara khusus, programmer akrab dengan jaringan komputer, yang juga merupakan grafik. Hal yang umum di sini adalah adanya titik-titik yang dihubungkan oleh garis. Jadi dalam jaringan komputer, titik-titiknya adalah server individual, dan garis-garisnya adalah berbagai jenis sinyal listrik. Di metro, yang pertama adalah stasiun, yang kedua adalah terowongan di antara mereka. Dalam teori graf, titik disebut puncak (node), dan garisnya adalah Tulang iga (busur). Dengan demikian, grafik adalah kumpulan simpul-simpul yang dihubungkan oleh sisi-sisinya.

Matematika beroperasi bukan dengan isi sesuatu, tetapi dengan strukturnya, mengabstraksikannya dari segala sesuatu yang diberikan secara keseluruhan. Dengan menggunakan teknik ini, kita dapat menyimpulkan bahwa beberapa objek adalah grafik. Dan karena teori graf adalah bagian dari matematika, sama sekali tidak ada bedanya dengan teori graf pada prinsipnya; satu-satunya hal yang penting adalah apakah itu suatu grafik, yaitu apakah ia memiliki sifat-sifat yang diperlukan untuk grafik. Oleh karena itu, sebelum memberikan contoh, kita soroti pada objek yang kita pertimbangkan hanya apa yang menurut kita memungkinkan kita menunjukkan analogi, kita mencari kesamaannya.

Mari kita kembali ke jaringan komputer. Ia memiliki topologi tertentu, dan secara konvensional dapat digambarkan sebagai sejumlah komputer dan jalur yang menghubungkannya. Gambar di bawah menunjukkan topologi terhubung penuh sebagai contoh.

Ini pada dasarnya adalah grafik. Lima komputer adalah simpulnya, dan koneksi (jalur sinyal) di antara mereka adalah tepinya. Dengan mengganti komputer dengan simpul, kita mendapatkan objek matematika - grafik, yang memiliki 10 sisi dan 5 simpul. Simpul dapat diberi nomor dengan cara apa pun, dan tidak harus seperti yang ditunjukkan pada gambar. Perlu dicatat bahwa contoh ini tidak menggunakan satu perulangan, yaitu suatu sisi yang meninggalkan suatu simpul dan segera memasukinya, tetapi perulangan dapat terjadi dalam masalah.

Berikut beberapa notasi penting yang digunakan dalam teori graf:

• G=(V, E), di sini G adalah grafnya, V adalah simpulnya, dan E adalah sisinya;
• |V| – urutan (jumlah simpul);
• |E| – ukuran grafik (jumlah sisi).

Dalam kasus kami (Gbr. 1) |V|=5, |E|=10;

Jika ada simpul lain yang dapat diakses dari simpul mana pun, maka graf tersebut disebut tidak berorientasi grafik terhubung (Gbr. 1). Jika graf tersebut terhubung, tetapi syarat tersebut tidak terpenuhi, maka graf tersebut disebut berorientasi atau digraf (Gbr. 2).

Graf berarah dan graf tidak berarah mempunyai konsep derajat simpul. Gelar tertinggi adalah jumlah sisi yang menghubungkannya ke simpul lain. Jumlah semua derajat suatu graf sama dengan dua kali jumlah seluruh sisinya. Untuk Gambar 2, jumlah semua pangkat adalah 20.

Dalam digraf, tidak seperti graf tak berarah, perpindahan dari simpul h ke simpul s tanpa simpul perantara dapat dilakukan hanya jika suatu sisi meninggalkan h dan memasuki s, tetapi tidak sebaliknya.

Graf berarah mempunyai notasi sebagai berikut:

G=(V, A), dengan V adalah simpul, A adalah sisi berarah.

Jenis grafik yang ketiga adalah Campuran grafik (Gbr. 3). Mereka memiliki tepi terarah dan tidak terarah. Secara formal, graf campuran ditulis seperti ini: G=(V, E, A), dimana setiap huruf dalam tanda kurung memiliki arti yang sama dengan yang diberikan sebelumnya.

Pada grafik pada Gambar 3, ada busur yang berarah [(e, a), (e, c), (a, b), (c, a), (d, b)], ada pula yang tidak berarah [(e, d), (e, b), (d, c)…].

Sekilas, dua grafik atau lebih mungkin tampak berbeda strukturnya, hal ini disebabkan karena representasinya yang berbeda. Namun tidak selalu demikian. Mari kita ambil dua grafik (Gbr. 4).

Mereka setara satu sama lain, karena tanpa mengubah struktur satu grafik, Anda dapat membuat grafik lainnya. Grafik seperti ini disebut isomorfis, yaitu, memiliki sifat bahwa setiap simpul dengan sejumlah sisi pada suatu graf mempunyai simpul yang identik pada graf lainnya. Gambar 4 menunjukkan dua grafik isomorfik.

Bila setiap sisi suatu graf dikaitkan dengan nilai tertentu yang disebut bobot sisi tersebut, maka graf tersebut tergantung. Dalam tugas yang berbeda, berbagai jenis pengukuran dapat bertindak sebagai bobot, misalnya panjang, harga, rute, dll. Dalam representasi grafis dari suatu grafik, nilai bobot biasanya ditunjukkan di sebelah tepinya.

Dalam grafik mana pun yang telah kami pertimbangkan, dimungkinkan untuk memilih jalur dan, terlebih lagi, lebih dari satu. Jalur adalah barisan simpul-simpul yang masing-masing simpul terhubung ke simpul berikutnya melalui suatu sisi. Jika simpul pertama dan simpul terakhir berhimpitan, maka jalur tersebut disebut siklus. Panjang suatu lintasan ditentukan oleh jumlah sisi yang menyusunnya. Misalnya pada Gambar 4.a lintasannya adalah barisan [(e), (a), (b), (c)]. Jalur ini merupakan subgraf, karena berlaku definisi yang terakhir, yaitu: graf G'=(V', E') adalah subgraf dari graf G=(V, E) hanya jika V' dan E' milik V, E.

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

1. Teori grafik. Konsep dasar

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 .

1. Karakteristik grafik

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

"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-simpul grafik web didistribusikan menurut hukum tertentu: proporsi situs (simpul) dengan banyak tautan (tepi) kecil, dan pangsa situs dengan sejumlah kecil tautan 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. “Sains”, 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

Institusi pendidikan kota

"Sekolah Menengah No. 6"

Abstrak dengan topik:

"Teori grafik"

Disiapkan oleh: Ekaterina Mayorova, kelas 8G

Guru: Malova Tatyana Alekseevna

I. Pendahuluan

II. Bagian utama.

1. Sejarah munculnya teori graf.

2. Beberapa permasalahan teori graf.

2.1 Masalah logika

2.2 Masalah konektivitas.

2.3 Soal menggunakan teorema Euler pada simpul ganjil

3. Penerapan teori graf dalam berbagai bidang kegiatan.

3.1.Grafik dan informasi

3.2.Grafik dan kimia.

3.3.Grafik dan biologi

3.4.Grafik dan fisika

AKU AKU AKU. Kesimpulan.

IV. Bibliografi.

I. Pendahuluan.

Saya memilih topik ini karena topik ini telah dan masih relevan di zaman kita.

Saat ini, grafik digunakan hampir di setiap cabang ilmu pengetahuan dan teknologi. Dalam fisika - dalam konstruksi sirkuit listrik, dalam kimia dan biologi

Saat mempelajari molekul dan rantainya, dalam geografi - saat menggambar peta, dalam sejarah - saat menyusun silsilah,

dalam geometri - dalam gambar poligon, polihedron, figur spasial, dalam ekonomi - ketika memecahkan masalah tentang memilih jalur optimal untuk arus angkutan barang (maskapai penerbangan, metro, skema kereta api).

Grafik adalah diagram blok program komputer dan jadwal pembangunan jaringan. Dengan menggunakan grafik, masalah penunjukan posisi terpecahkan. Yaitu: jika ada beberapa jabatan yang kosong dan sekelompok orang yang bersedia mengisinya, dan masing-masing pelamar memenuhi syarat untuk beberapa jabatan, lalu dalam kondisi apa masing-masing pelamar dapat memperoleh pekerjaan di salah satu spesialisasinya?

Teori graf tidak dipelajari dalam kurikulum sekolah, tetapi banyak digunakan dalam memecahkan masalah olimpiade matematika.

II. 1. Sejarah teori graf

Setelah mempelajari informasi dari sumber internet, saya menemukan fakta menarik berikut tentang sejarah teori graf.

Sejarah teori ini dapat ditelusuri melalui korespondensi ilmuwan besar tersebut. Di dalamnya, ia melaporkan bahwa ia ditawari masalah tujuh jembatan Koenigsberg. Pertanyaannya adalah apakah ada orang yang bisa mengitarinya terus menerus, hanya melewati satu kali melewati setiap jembatan. Dan dia segera diberitahu bahwa belum ada seorang pun yang mampu melakukan hal ini, tetapi tidak ada yang membuktikan bahwa hal itu tidak mungkin. Pertanyaan ini sepertinya patut mendapat perhatiannya karena “...Baik geometri, aljabar, maupun seni kombinatorial tidak cukup untuk menyelesaikannya...”. Setelah berpikir panjang, ia menemukan sebuah aturan yang mudah, berdasarkan pada bukti yang sepenuhnya meyakinkan, dengan bantuan yang memungkinkan untuk menentukan dalam semua masalah semacam ini apakah jalan memutar seperti itu dapat dilakukan melalui sejumlah dan sejumlah jembatan yang terletak atau bukan. Jembatan Koenigsberg disusun sedemikian rupa sehingga dapat direpresentasikan dalam sebuah gambar, dimana A melambangkan sebuah pulau, dan B, C dan D merupakan bagian dari benua yang dipisahkan satu sama lain oleh cabang-cabang sungai. Ketujuh jembatan tersebut ditandai dengan huruf a, b, c, d, e, f, g.

http://www.cba.upc.edu/projects/logos/Euler_logo.png Jembatan Königsberg.

Ahli matematika itu menulis bahwa peralihan itu mungkin terjadi jika tidak ada lebih dari dua daerah di pertigaan sungai, yang dituju oleh jumlah jembatan ganjil.

Untuk memudahkan membayangkannya, kita akan menghapus jembatan yang sudah dilalui pada gambar. Sangat mudah untuk memeriksa bahwa jika Anda 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 mengarah ke jumlah jembatan ganjil. Dan jika ada daerah yang jumlah jembatannya ganjil, maka kami akan berlokasi di salah satunya. Terus bergerak seperti ini, kita akan melintasi semua jembatan satu kali.

Kisah jembatan kota Königsberg memiliki kelanjutan modern. Dalam beberapa buku teks matematika atau pada bahan tambahan (lampiran) buku teks tersebut, Anda dapat menemukan masalah yang penyelesaiannya justru didasarkan pada metode yang dikemukakan oleh Euler.

Saya menyadari bahwa dalam penalarannya, Euler sampai pada kesimpulan berikut:

Banyaknya simpul ganjil (simpul yang ujung-ujungnya berjumlah ganjil) pada suatu graf harus genap. Tidak mungkin ada graf yang mempunyai jumlah simpul ganjil.

Jika semua simpul pada suatu graf genap, maka Anda dapat menggambar sebuah grafik tanpa mengangkat pensil dari kertas, dan Anda dapat memulai dari simpul mana pun pada grafik dan mengakhirinya pada simpul yang sama.

Graf yang mempunyai lebih dari dua simpul ganjil tidak dapat digambar dengan satu garis.

Grafik jembatan Königsberg memiliki empat simpul ganjil (yaitu semuanya), oleh karena itu tidak mungkin untuk berjalan melintasi semua jembatan tanpa melewati salah satunya dua kali.

Setelah mempelajari kesimpulan ini, saya memutuskan untuk mengujinya menggunakan contoh soal lain dari bagian teori graf.

Sebagai kesimpulan, saya perhatikan bahwa 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. Beberapa permasalahan teori graf

Tidak banyak masalah dalam teori graf. Saya telah meninjau materinya

Sumber daya dan buku internet, menganalisis tugas-tugas yang diusulkan di sana, mencoba mensistematisasikannya dan mengidentifikasi darinya berbagai tugas, menurut pendapat saya, yang dapat diselesaikan dengan menggunakan grafik:

^2.1 Masalah logika

Soal 1. Arkady, Boris. Vladimir, Grigory dan Dmitry berjabat tangan ketika mereka bertemu (masing-masing berjabat tangan satu kali). Berapa banyak jabat tangan yang dilakukan?
Misalkan masing-masing dari lima orang muda bersesuaian dengan suatu titik tertentu pada bidang yang diberi nama dengan huruf pertama namanya (Gbr. 2), dan biarlah jabat tangan yang dilakukan menjadi ruas atau bagian dari kurva yang menghubungkan titik-titik tertentu - nama (Gbr. .

Grafik nol dengan lima simpul

Graf tidak lengkap dengan lima simpul

http://school-sector.relarn.ru/dckt/projects/ctrana/graf/gr1.htm

Titik A, B, C, D, E disebut titik sudut pada grafik, dan ruas garis yang menghubungkan titik-titik tersebut disebut sisi grafik. Saat menggambarkan grafik dalam gambar atau diagram, segmennya bisa lurus atau lengkung; Panjang segmen dan lokasi titik-titiknya berubah-ubah.

Mari kita perhatikan proses menghubungkan titik A, B, C, D, D dengan rusuk.
1. Situasi yang berhubungan dengan momen belum terjadinya jabat tangan adalah diagram titik yang ditunjukkan pada Gambar 2. Diagram seperti itu, yang terdiri dari simpul-simpul “terisolasi”, disebut grafik nol.
2. Keadaan belum semua jabat tangan selesai dapat digambarkan secara skematis, misalnya menggunakan Gambar 3: jabat tangan A dan B, A dan D, D dan D, C dan E telah dijabat.
Graf yang semua kemungkinan sisinya tidak dibangun disebut graf tidak lengkap.
3. Gambar 4 menunjukkan grafik yang sesuai dengan semua jabat tangan yang telah selesai. Grafik ini merupakan grafik lengkap.

Grafik lengkap dengan lima simpul

Soal 2. Papan berbentuk salib ganda, diperoleh jika sel sudut dihilangkan dari persegi 4x4.

Apakah mungkin untuk melewatinya dengan menggerakkan ksatria catur dan kembali ke kotak semula, mengunjungi semua kotak tepat satu kali?

Solusi: Saya memberi nomor semua sel secara berurutan:

Dan sekarang, dengan menggunakan gambar tersebut, saya telah menunjukkan bahwa traversal tabel seperti itu, seperti yang ditunjukkan dalam kondisi, adalah mungkin:

Soal 3. Ada 15 telepon di kota Malenky. Apakah mungkin untuk menghubungkannya dengan kabel sehingga setiap telepon terhubung ke lima telepon lainnya?

Solusi: Saya berasumsi bahwa koneksi telepon seperti itu dimungkinkan. Kemudian saya membayangkan sebuah grafik yang simpul-simpulnya melambangkan telepon, dan ujung-ujungnya melambangkan kabel-kabel yang menghubungkannya. Saya menghitung berapa banyak kabel yang akan ada. Setiap telepon memiliki tepat 5 kabel yang terhubung, mis. derajat setiap simpul pada grafik adalah 5. Untuk mencari jumlah kabel, Anda perlu menjumlahkan derajat semua simpul pada grafik dan membagi hasilnya dengan 2 (karena setiap kawat memiliki dua ujung, maka saat menjumlahkan derajatnya, tiap kawat diambil 2 kali). Tapi jumlah kabelnya akan berbeda. Tapi angka ini bukan bilangan bulat. Ini berarti asumsi saya bahwa Anda dapat menghubungkan setiap ponsel dengan lima ponsel lainnya ternyata salah.

Menjawab. Tidak mungkin menghubungkan telepon dengan cara ini.

Saat memecahkan masalah ini, saya menemukan cara menghitung jumlah sisi suatu grafik, mengetahui derajat semua simpulnya. Untuk melakukan ini, Anda perlu menjumlahkan derajat simpul dan membagi hasilnya dengan dua.

Soal 4. Ada 100 kota di negara bagian ini, 4 jalan keluar dari setiap kota. Berapa banyak jalan yang ada di negara bagian ini?

Larutan. Mari kita hitung jumlah jalan yang meninggalkan kota - 100. 4 = 400. Namun, dengan perhitungan ini, setiap jalan dihitung 2 kali - meninggalkan satu kota dan memasuki kota lain. Ini berarti jumlah total jalan dua kali lebih sedikit, yaitu. 200.

Soal 5. Dapatkah suatu negara bagian yang mempunyai tepat 3 jalan keluar dari setiap kota mempunyai tepat 100 jalan?

Larutan. Saya akan menghitung jumlah kota. Banyaknya jalan sama dengan banyaknya kota x, dikalikan 3 (banyaknya jalan yang keluar dari setiap kota) dan dibagi 2. Maka 100 = 3x/2 => 3x = 200, tidak bisa dengan x natural. Artinya, tidak mungkin ada 100 jalan dalam kondisi seperti itu.

^ 2.2 Masalah konektivitas.

Ada konsep penting lainnya yang berkaitan dengan grafik - konsep konektivitas.

Suatu graf disebut terhubung jika dua simpulnya dapat dihubungkan oleh suatu jalur, yaitu urutan tepi yang berkesinambungan.

Ada beberapa permasalahan yang penyelesaiannya didasarkan pada konsep konektivitas graf.

^ Grafik Euler.

Saya sering menemui masalah yang mengharuskan saya menggambar suatu bentuk tanpa mengangkat pensil dari kertas dan menggambar setiap garis hanya sekali. Ternyata masalah seperti itu tidak selalu bisa diselesaikan, mis. Ada angka-angka yang tidak dapat digambar menggunakan metode ini. Pertanyaan tentang solvabilitas masalah tersebut juga termasuk dalam teori graf. Ini pertama kali dieksplorasi pada tahun 1736 oleh matematikawan besar Jerman Leonhard Euler, memecahkan masalah jembatan Königsberg. Oleh karena itu, graf yang dapat digambarkan dengan cara ini disebut graf Euler.

Soal 1. Apakah mungkin menggambar grafik yang ditunjukkan pada gambar tanpa mengangkat pensil dari kertas dan menggambar setiap sisinya tepat satu kali?

Larutan. Jika saya menggambar grafik seperti yang dinyatakan dalam kondisi, maka saya akan memasuki setiap titik, kecuali titik awal dan akhir, dengan jumlah yang sama dengan saat kita keluar. Artinya, semua simpul pada grafik, kecuali dua, harus genap. Grafik kita memiliki tiga simpul ganjil, sehingga tidak dapat digambar dengan cara yang ditentukan dalam kondisi.

^2.3 Soal menggunakan teorema Euler pada simpul ganjil

Soal 1. Ada 30 orang di kelas. Mungkinkah 9 orang punya 3 teman, 11 punya 4 teman, dan 10 punya 5 teman?

Menjawab. Tidak (menurut teorema paritas jumlah simpul ganjil).

Soal 2. Raja memiliki 19 baron bawahan. Mungkinkah setiap baron bawahan memiliki 1, 5, atau 9 baron tetangga?

Menjawab. Tidak, dia tidak bisa. Jika tidak, hasilnya akan berupa graf lingkungan baron dengan jumlah simpul ganjil.

3. Penerapan teori graf.

Semakin saya mempelajari teori graf, semakin saya takjub dengan beragamnya penerapan teori ini. Grafik digunakan dalam berbagai cabang ilmu pengetahuan.

3.1.Grafik dan informasi

Grafik memainkan peran yang sangat penting dalam teori informasi. Misalkan sejumlah pesan tertentu perlu dikodekan dalam formulir

barisan berhingga dengan panjang bervariasi yang terdiri dari nol dan satu. Jika probabilitas kata kode diberikan, maka kode terbaik dianggap kode yang rata-rata panjang kata minimal dibandingkan dengan distribusi probabilitas lainnya.

3.2.Grafik dan kimia.

Teori graf dalam kimia digunakan untuk menyelesaikan berbagai masalah teoritis dan terapan. Penerapan teori graf didasarkan pada konstruksi dan analisis berbagai kelas graf kimia dan teknologi kimia, yang disebut juga topologi, yaitu. model yang hanya memperhitungkan sifat hubungan antar simpul. Tepi dan simpul grafik ini mencerminkan konsep, fenomena, proses atau objek kimia dan teknologi kimia dan, karenanya, hubungan kualitatif dan kuantitatif atau hubungan tertentu di antara keduanya.

3.3.Grafik dan biologi

Grafik memainkan peran besar dalam teori biologis tentang proses percabangan. Untuk mempermudah, saya hanya akan menampilkan satu jenis percabangan

proses – reproduksi bakteri. Mari kita asumsikan itu setelah waktu tertentu

periode waktu tertentu, setiap bakteri akan membelah menjadi dua bakteri baru, atau

meninggal. Kemudian untuk keturunan satu bakteri saya akan mendapatkan pohon biner.

Kami hanya akan tertarik pada satu pertanyaan: dalam berapa banyak kasus nth

satu generasi dari satu bakteri mempunyai tepat k keturunan? Rasio yang dihitung secara matematis berdasarkan nilai anggota barisan sebelumnya, yang menunjukkan jumlah kasus yang diperlukan, dalam biologi dikenal sebagai proses Galton-Watson. Ini dapat dianggap sebagai kasus khusus dari banyak rumus umum.

3.4.Grafik dan fisika

Sampai saat ini, salah satu tugas tersulit dan membosankan bagi amatir radio adalah merancang sirkuit cetak.

Sirkuit tercetak adalah pelat yang terbuat dari beberapa bahan dielektrik.

(bahan isolasi), yang berbentuk strip logam

jalur telah terhapus. Jalur-jalur tersebut hanya dapat berpotongan pada titik-titik tertentu di mana elemen-elemen yang diperlukan dipasang; perpotongannya di tempat lain akan menyebabkan penutupan rangkaian listrik.

Untuk menyelesaikan masalah ini, perlu menggambar grafik datar dengan simpul-simpul pada titik-titik yang ditunjukkan.

Saat mempelajari materi ini, saya mempelajari bidang penerapan teori graf dan menyimpulkan bahwa cabang matematika ini adalah salah satu cabang terpenting yang digunakan dalam kehidupan kita sehari-hari, yang seringkali tidak kita sadari.

AKU AKU AKU. Kesimpulan

Grafik adalah objek matematika luar biasa yang dapat digunakan untuk memecahkan masalah matematika, ekonomi, dan logika. Anda juga dapat memecahkan berbagai teka-teki dan menyederhanakan kondisi masalah dalam fisika, kimia, elektronik, dan otomatisasi. Teori graf sendiri merupakan bagian dari topologi dan kombinatorik.

Oleh karena itu, saya menyimpulkan bahwa mempelajari teori graf penting untuk perkembangan komprehensif seorang siswa.

IV. Daftar literatur dan sumber daya Internet.

1. “Jurnal Pendidikan Soros” Nomor 11 Tahun 1996 (artikel “Grafik Datar”);

2. Kasatkin V. N. “Masalah matematika yang tidak biasa”, Kyiv, “sekolah Radyanska”

1987 (bagian 2);

3. Gardner M. "Rekreasi matematika", M. "Mir", 1972 (bab 35);

4. “Untuk membantu guru matematika”, Yoshkar-Ola, 1972 (artikel “Mempelajari unsur-unsur teori graf”);

5. Olehnik S. N., Nesterenko V., Potapov M. K. “Hiburan lama

Tugas", M. "Sains", 1988 (bagian 2, bagian 8; lampiran 4);

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

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

8. Zykov A. A. “Teori grafik terbatas”, Novosibirsk, “Nauka”, 1969;

9. Berge K. “Teori Graf dan Penerapannya”, M., IL, 1962;

10. Renyi A., “Trilogi tentang matematika”, M., “Mir”, 1980.

11.http://ru.wikipedia.org

12.http://www.xumuk.ru

13.http://www.seznaika.ru

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, 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 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 mengatasi masalah ini. Jika 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 dapat dimulai. 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 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 molekuler, yang hanya berisi semua simpul yang bersesuaian dengan atom C. Kompilasi kumpulan mol. pohon dan penetapan isomorfismenya memungkinkan untuk menentukan apa yang dikatakannya. struktur dan temukan jumlah total isomer alkana, alkena, dan alkuna

Jaringan protein

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

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

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

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

Contoh silsilah keluarga saya [Lampiran Gambar 12].

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

Penyelesaian masalah

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

Larutan:

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

Untuk kenyamanan solusi, kami menunjuk 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.

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

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

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

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

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

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

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

Aplikasi

Aplikasi

P

Beras. 6

Beras. 7

Beras. 8

aplikasi

Aplikasi

Aplikasi

Aplikasi

P

Beras. 14

aplikasi

Aplikasi

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

menjadi isomorfik jika ada yang saling identik

pemetaan nilai

: V 1 V 2

Terus?

(kamu , v ) ((kamu ), (v )) .

Jadi, graf yang hanya berbeda pada jumlah simpul dan sisinya adalah graf isomorfik. Isomorfisme graf merupakan relasi ekivalensi karena mempunyai sifat:

Refleksivitas -

G1,

dan keberatan

adalah fungsi yang identik.

Simetri.

dengan bijeksi

dengan bijeksi

Transitivitas.

G 1 G 2

keberatan

1,a

dengan bijeksi

lalu G G

dengan bijeksi

2 (1 ) .