Teori Graf
Teori graf mempelajari graf – struktur simpul yang dihubungkan oleh sisi – sebagai model matematis dari relasi berpasangan dan jaringan.
Definition
Studi matematis tentang graf, yang merupakan himpunan simpul bersama dengan himpunan sisi yang masing-masing menghubungkan sepasang simpul, dan tentang properti yang invarian di bawah struktur koneksi tersebut.
Scope
Bidang ini mencakup struktur, properti, dan parameter graf: konektivitas, jalur dan siklus, pohon, planaritas, pewarnaan, pencocokan, dan aliran, serta pertanyaan ekstremal dan probabilistik tentang bagaimana properti graf saling membatasi. Ini adalah inti dari matematika diskrit dan menyediakan bahasa untuk jaringan di seluruh ilmu komputer, riset operasi, serta ilmu alam dan sosial.
Sub-topics
Core questions
- Properti struktural apa yang mengikuti dari konektivitas, urutan derajat, atau struktur siklus suatu graf?
- Kapan suatu graf dapat digambar di bidang tanpa persilangan atau diwarnai dengan sedikit warna?
- Seberapa besar atau padat suatu graf dapat terbentuk sambil menghindari substruktur tertentu?
- Bagaimana jalur, pencocokan, dan aliran memungkinkan seseorang untuk mengoptimalkan suatu jaringan?
Key concepts
- Simpul, sisi, dan derajat
- Konektivitas dan komponen
- Jalur, siklus, dan pohon
- Planaritas
- Pewarnaan graf
- Pencocokan dan aliran
Clinical relevance
Graf memodelkan jaringan komunikasi dan transportasi, jaringan interaksi sosial dan biologis, struktur sirkuit dan ketergantungan, serta masalah penjadwalan, menjadikan teori graf sebagai alat fundamental dalam ilmu komputer dan riset operasi.
History
Teori graf berawal dari solusi Euler pada tahun 1736 untuk masalah jembatan Konigsberg dan berkembang pada abad ke-20 melalui karya tentang pewarnaan, konektivitas, serta metode probabilistik dan struktural dari Erdos, Tutte, dan lainnya.
Key figures
- Leonhard Euler
- William Tutte
- Bela Bollobas
Related topics
Seminal works
- diestel2017
- bollobas1998
Frequently asked questions
- Apa perbedaan antara graf dan jaringan?
- Graf adalah objek matematis abstrak dari simpul dan sisi; jaringan umumnya mengacu pada graf yang dilengkapi dengan data tambahan seperti bobot, kapasitas, atau arah yang memodelkan sistem nyata.
- Mengapa masalah jembatan Konigsberg penting?
- Pembuktian Euler bahwa tidak ada jalur yang dapat melintasi setiap tujuh jembatan tepat satu kali mengabstraksikan masalah tersebut menjadi simpul dan sisi, mendirikan teori graf dan topologi.