Pengantar Teori Graf

Bagaimana Anda memodelkan koneksi berpasangan antar objek? 

Dengan sebuah struktur matematika yang disebut graf. Inilah inti dari Teori Graf – studi tentang graf.  

Elemen mendasar dalam teori graf adalah vertex (juga disebut node/simpul) dan edge (juga disebut link/sisi). Sebuah simpul mewakili entitas atau titik individual dalam graf, sedangkan sisi menunjukkan koneksi atau hubungan antara dua simpul. Bersama-sama, komponen ini membentuk struktur graf, yang bisa berarah atau tak berarah, berbobot atau tak berbobot, bergantung pada sifat spesifik hubungan yang dimodelkan.

Dalam ilmu komputer, teori graf mendasari banyak algoritma dan struktur data yang digunakan untuk merepresentasikan jaringan seperti internet, jejaring sosial, dan sistem komunikasi. Teori ini juga menyediakan alat untuk menyelesaikan masalah terkait konektivitas jaringan, pencarian jalur, dan optimasi, serta menjadi dasar untuk memahami berbagai struktur dan konsep matematika seperti pohon (tree), siklus, dan graf planar.

Dalam artikel ini, kami akan mengajarkan hal-hal yang perlu Anda ketahui untuk mulai mempelajari teori graf.  

Dibuat oleh penulis menggunakan Midjourney

Apa itu Teori Graf?

Teori graf adalah cabang matematika yang mengkaji sifat dan penerapan graf. Sebuah graf mendefinisikan sekumpulan objek yang disebut simpul (vertices/nodes) yang dihubungkan oleh sisi (edges/links). 

Tujuan utama teori graf adalah memahami struktur graf-graf tersebut dan mengeksplorasi berbagai masalah terkait konektivitas, pencarian jalur, dan optimasi jaringan.

Dengan menganalisis hubungan-hubungan ini, teori graf memungkinkan kita memperoleh wawasan tentang banyak masalah dunia nyata di berbagai bidang.

Dari mana asal teori graf?

Asal-usul teori graf bermula pada abad ke-18 melalui karya matematikawan Swiss, Leonhard Euler. Solusi Euler untuk masalah jembatan Königsberg pada tahun 1736 dianggap sebagai salah satu masalah pertama dalam teori graf. Masalah ini melibatkan pencarian rute berjalan di kota Königsberg yang melintasi masing-masing dari tujuh jembatannya tepat satu kali. Pendekatan Euler meletakkan dasar bagi apa yang kemudian menjadi kajian formal tentang graf.

Pada abad ke-19 dan ke-20, teori graf berkembang pesat dengan kontribusi dari matematikawan seperti Carl Friedrich Gauss, yang mengeksplorasi sifat poliedra, dan para peneliti berikutnya yang memformalkan konsep serta mengembangkan algoritma untuk masalah terkait graf. 

Munculnya ilmu komputer pada pertengahan abad ke-20 semakin mempercepat pertumbuhan teori graf, sehingga penerapannya meluas dalam algoritma komputer, analisis jaringan, dan struktur data.

Konsep dasar teori graf

Memahami dasar-dasar teori graf memberikan landasan untuk mengeksplorasi topik yang lebih lanjut di bidang ini. Jadi untuk memulai, mari kita pasang fondasinya… 

Graf sebagai Pasangan Terurut

Secara formal, sebuah graf didefinisikan sebagai pasangan terurut G = (V, E), dengan:

• V adalah himpunan simpul (vertices/nodes) yang merepresentasikan entitas individual dalam graf.
• E adalah himpunan sisi (edges/links) yang merepresentasikan koneksi antar pasangan simpul.

Simpul (V) dan Sisi (E)

• Simpul (V): Unit atau titik fundamental dalam graf. Setiap simpul mewakili entitas atau lokasi dalam struktur yang dimodelkan.

• Sisi (E): Koneksi atau hubungan antar pasangan simpul. Setiap sisi menghubungkan dua simpul, menandakan adanya hubungan atau jalur di antara keduanya.

Jenis-jenis Sisi

• Sisi Berarah: Dalam graf berarah (directed graph/digraf), sisi memiliki arah, artinya sisi berjalan dari satu simpul ke simpul tertentu lainnya. Arah ini sering direpresentasikan dengan panah. Sisi berarah berguna untuk memodelkan hubungan asimetris, seperti arus lalu lintas atau kendala precedensi dalam penjadwalan.

• Sisi Tak Berarah: Dalam graf tak berarah, sisi tidak memiliki arah dan sekadar menghubungkan dua simpul. Jenis graf ini digunakan untuk merepresentasikan hubungan simetris, seperti pertemanan timbal balik atau koneksi dalam jaringan di mana arah tidak signifikan.

Istilah dan Konsep Dasar Teori Graf

Sekarang, mari kita definisikan beberapa istilah dan konsep dasar: 

Simpul (Node)

Konsep ini merepresentasikan entitas atau titik individual dalam struktur graf. Misalnya, dalam graf jejaring sosial, setiap orang dapat direpresentasikan sebagai sebuah simpul.

Derajat Suatu Simpul

Derajat sebuah simpul adalah jumlah sisi yang terhubung dengannya. Hal ini memberi wawasan tentang konektivitas dan tingkat kepentingannya dalam graf. Cara terbaik untuk memvisualisasikannya adalah membayangkan seseorang, direpresentasikan sebagai simpul, dalam jejaring sosial. Jika ada banyak sisi dari simpul tersebut, kita akan mengatakan simpul itu memiliki “derajat tinggi,” yang juga menandakan orang yang sangat berpengaruh. Jika kita memodelkan jaringan transportasi, simpul berderajat tinggi akan menunjukkan bahwa simpul tersebut adalah hub pusat dalam jaringan, yang terhubung langsung ke sebagian besar lokasi lain.   

Jalur

Sebuah jalur dalam graf adalah urutan simpul di mana setiap pasangan berurutan terhubung oleh sebuah sisi. Jalur bisa sederhana (tanpa pengulangan simpul) atau umum (memungkinkan pengulangan). Misalnya, dalam graf dengan simpul A, B, C, dan D, sebuah jalur bisa berupa A → B → C → D, di mana setiap simpul terhubung ke simpul berikutnya oleh sebuah sisi.

Siklus

Siklus adalah jalur yang dimulai dan diakhiri pada simpul yang sama, tanpa pengulangan simpul atau sisi lainnya. Siklus dapat sederhana (tanpa pengulangan sisi atau simpul kecuali titik awal dan akhir) atau umum. Contohnya: dalam graf dengan simpul A, B, C, dan D, sebuah siklus sederhana bisa berupa A → B → C → D → A.

Graf Terhubung

Sebuah graf disebut terhubung jika ada jalur antara setiap pasangan simpul. Dengan kata lain, setiap simpul dalam graf terhubung dapat mencapai setiap simpul lainnya melalui suatu rangkaian sisi. Contoh yang baik adalah graf jejaring sosial di mana setiap orang dapat dijangkau dari orang lain mana pun.

Jenis-jenis Graf

Teori graf mencakup berbagai jenis graf, masing-masing cocok untuk aplikasi dan analisis yang berbeda. Pada bagian ini, kita akan mengeksplorasi jenis-jenis tersebut, membahas struktur dasarnya, dan memberikan contoh penerapannya. Ini akan membantu Anda memahami kapan menggunakan setiap jenis untuk menyelesaikan masalah spesifik dan memodelkan skenario dunia nyata secara akurat.

Graf Sederhana

Visualisasi graf sederhana Sumber: Wikipedia

Graf sederhana adalah jenis graf yang tidak memiliki sisi ganda (lebih dari satu sisi antara sepasang simpul) atau gelang (loop, sisi yang menghubungkan simpul ke dirinya sendiri). Setiap sisi dalam graf sederhana menghubungkan dua simpul yang berbeda.

Contoh:

• Jejaring sosial dasar di mana setiap pertemanan direpresentasikan oleh satu tautan antara dua orang.
• Peta kota yang dihubungkan oleh jalan tunggal langsung tanpa rute ganda atau koneksi ke diri sendiri.

Multigraf

Visualisasi Multigraf dengan sisi ganda berwarna merah, dan beberapa gelang berwarna biru Sumber: Wikipedia

Multigraf memungkinkan adanya beberapa sisi (sisi paralel) antara pasangan simpul yang sama dan juga dapat mencakup gelang. Jenis graf ini dapat merepresentasikan situasi di mana terdapat banyak interaksi atau koneksi antara entitas.

Contoh:

• Jaringan transportasi di mana beberapa maskapai mengoperasikan penerbangan antara kota yang sama.
• Jaringan komunikasi dengan beberapa kanal yang menghubungkan pasangan simpul komunikasi yang sama.

Graf Berbobot

Visualisasi graf berbobot Sumber: Hyperskill

Dalam graf berbobot, setiap sisi memiliki bobot atau biaya terkait, yang merepresentasikan ukuran kuantitatif seperti jarak, waktu, atau kapasitas. Graf berbobot digunakan untuk memodelkan masalah ketika sisi memiliki kekuatan atau biaya yang berbeda-beda.

Aplikasi:

• Dalam peta kota yang dihubungkan oleh jalan, bobot dapat merepresentasikan jarak atau waktu tempuh antar kota.
• Dalam masalah optimasi jaringan, bobot bisa merepresentasikan bandwidth atau biaya tautan komunikasi.

Graf Berarah (Digraf)

Visualisasi graf berarah Sumber: Wikipedia

Graf berarah, atau digraf, memiliki sisi dengan arah tertentu, yang berarti setiap sisi berjalan dari satu simpul ke simpul lain yang berbeda. Arah ini sering ditunjukkan dengan panah, menandakan aliran atau hubungan satu arah.

Kasus penggunaan:

• Diagram alur kerja di mana tugas harus diselesaikan dalam urutan tertentu.
• Struktur tautan halaman web, di mana hyperlink menunjuk dari satu halaman ke halaman lain, merepresentasikan koneksi satu arah.

Graf Tak Berarah

Visualisasi graf tak berarah Sumber: Baeldung

Dalam graf tak berarah, sisi tidak memiliki arah. Sebuah sisi sekadar menghubungkan dua simpul, dan hubungannya bersifat timbal balik atau dua arah. Urutan simpul dalam sebuah sisi tidak penting.

Contoh:

• Jaringan pertemanan di mana pertemanan bersifat timbal balik, dan koneksinya dua arah.
• Peta jalan tak berarah di mana jalan menghubungkan kota-kota ke dua arah tanpa menentukan arah tertentu.

Teori Graf Pohon

Sebuah pohon (tree) adalah jenis graf yang terhubung dan asiklik, artinya tidak mengandung siklus. Sebuah pohon dengan $$n$$ simpul memiliki tepat $$n−1$$ sisi. Setiap pasangan simpul dalam pohon terhubung oleh tepat satu jalur, yang memastikan adanya jalur unik antara dua simpul mana pun.

Berikut ringkasan cepat sifat-sifat graf pohon: 

• Terhubung. Ada jalur antara setiap pasangan simpul.
• Asiklik. Tidak ada siklus, sehingga tidak terdapat lintasan tertutup.
• Jalur unik. Terdapat tepat satu jalur antara dua simpul mana pun, yang menyiratkan bahwa graf tersebut terhubung secara minimal.
• Jumlah sisi. Sebuah pohon dengan $$n$$ simpul memiliki $$n−1$$ sisi.
• Subpohon: Setiap subset dari sebuah pohon, termasuk satu simpul, merupakan pohon itu sendiri, yang disebut subpohon.
• Daun (leaf nodes). Simpul dengan tepat satu sisi disebut daun atau leaf node. Mereka adalah titik ujung dari pohon.

Bagaimana graf pohon berbeda dari graf lainnya? 

Berbeda dengan graf umum, pohon tidak mengandung siklus. Ini berarti graf apa pun yang memiliki siklus tidak dapat diklasifikasikan sebagai pohon. 

Sebuah pohon dengan $$n$$ simpul memiliki tepat $$n−1$$ sisi, sedangkan graf umum dapat memiliki jumlah sisi yang bervariasi, termasuk sisi ganda dan gelang. Perbedaan lain adalah pohon selalu terhubung, sedangkan graf umum bisa tak terhubung, terdiri dari beberapa komponen yang masing-masing bisa berupa pohon. 

Selain itu, dalam sebuah pohon, terdapat tepat satu jalur antara dua simpul mana pun, tidak seperti graf lain yang dapat memiliki banyak jalur antar simpul, khususnya pada graf yang mengandung siklus atau sisi ganda.

Aplikasi

Pohon bersifat fundamental baik dalam aspek teoretis maupun praktis komputasi dan pengorganisasian data. Pohon menawarkan solusi yang sangat efisien untuk banyak masalah struktural dan algoritmik. Misalnya: 

Struktur data

• Pohon Biner: Digunakan dalam ilmu komputer untuk mengorganisasi data secara hierarkis. Contohnya termasuk binary search tree, yang memfasilitasi pengambilan dan pengurutan data yang cepat.
• Heap: Jenis pohon biner yang digunakan dalam priority queue untuk mengelola dan mengambil elemen maksimum atau minimum secara efisien.
• B-Tree: Digunakan dalam basis data dan sistem berkas untuk pengambilan dan penyimpanan data yang efisien, mendukung operasi seperti penyisipan, penghapusan, dan pencarian.

Perancangan jaringan

• Perutean: Pohon digunakan dalam protokol perutean jaringan (seperti spanning tree) untuk menentukan jalur paling efisien bagi transmisi data di seluruh jaringan.
• Broadcasting: Dalam perancangan jaringan, struktur pohon membantu penyiaran data secara efisien, memastikan data tersebar ke semua simpul dengan redundansi minimal.

Representasi hierarki

• Sistem Berkas: Sistem berkas sering menggunakan struktur pohon untuk merepresentasikan direktori dan subdirektori, mencerminkan organisasi berkas secara hierarkis.
• Bagan Organisasi: Pohon digunakan untuk memodelkan hierarki organisasi, menunjukkan struktur pelaporan dan hubungan antar peran.

Parsing dan analisis sintaksis

• Abstract Syntax Tree (AST): Digunakan dalam kompilator dan interpreter untuk merepresentasikan struktur sintaksis kode sumber. AST memfasilitasi pemeriksaan sintaksis dan optimasi kode.

Penerapan Teori Graf

Teori graf memiliki penerapan yang luas di berbagai bidang. Teori ini berperan penting dalam menyelesaikan masalah kompleks dan mengoptimalkan sistem. Contohnya dapat dilihat pada penerapan berikut: 

Ilmu komputer: jaringan, algoritma, dan struktur data

Teori graf menjadi dasar dalam merancang dan menganalisis sistem jaringan, mengembangkan algoritma, dan menyusun data dalam ilmu komputer. Misalnya, jaringan sangat bergantung pada teori graf untuk memodelkan dan mengelola koneksi antar perangkat. Khususnya, topologi jaringan direpresentasikan sebagai graf untuk mengoptimalkan transmisi data dan perutean. 

Algoritma seperti Dijkstra dan Kruskal digunakan masing-masing untuk menyelesaikan masalah jalur terpendek dan pohon merentang minimum. Selain itu, teori graf mendasari struktur data seperti daftar adjacency dan matriks, yang penting untuk manipulasi dan pengambilan data yang efisien.

Biologi: memodelkan jaringan biologis

Teori graf juga sangat berperan dalam biologi. Teori ini digunakan untuk memodelkan dan menganalisis jaringan biologis yang kompleks, seperti: 

• Jaringan interaksi protein-protein
• Jalur metabolik
• Jaringan regulasi gen

Jaringan-jaringan ini direpresentasikan sebagai graf di mana simpul menyatakan entitas biologis (misalnya protein, gen) dan sisi merepresentasikan interaksi atau hubungan di antara mereka. 

Pendekatan ini membantu peneliti memahami hubungan rumit dalam sistem biologis, memprediksi hasil fungsional, dan mengidentifikasi target potensial untuk pengembangan obat.

Ilmu sosial: analisis jejaring sosial

Dalam ilmu sosial, teori graf digunakan untuk menganalisis jejaring sosial, di mana individu direpresentasikan sebagai simpul dan interaksi atau hubungan mereka digambarkan sebagai sisi. 

Analisis ini membantu memahami struktur sosial, pola pengaruh, dan dinamika komunitas. Menerapkan konsep seperti sentralitas dan konektivitas memungkinkan peneliti mengidentifikasi pengaruh kunci, mempelajari penyebaran informasi, dan menganalisis perilaku sosial.

Transportasi: arus lalu lintas dan perencanaan perkotaan 

Kebanyakan orang tidak mengetahui ini, tetapi jalan, persimpangan, dan rute angkutan dimodelkan sebagai graf untuk: 

• Mengoptimalkan arus lalu lintas
• Mengurangi kemacetan
• Meningkatkan perencanaan rute. 

Algoritma berbasis graf membantu merancang jaringan transportasi yang efisien, mengelola sistem angkutan umum, dan merencanakan infrastruktur perkotaan. Menganalisis jaringan-jaringan ini membantu perencana mengambil keputusan yang tepat untuk meningkatkan mobilitas dan konektivitas dalam kota.

Langkah demi Langkah Membangun dan Menganalisis Graf Sederhana

Anda sudah menguasai dasar-dasarnya, dan Anda memahami penerapan teori graf. 

Sekarang, Anda siap membuat dan menganalisis graf sederhana Anda sendiri. Demi kesederhanaan, kami membagi panduan langkah demi langkah ini menjadi dua bagian: 

• Konstruksi 
• Analisis

Bagian paling logis untuk dimulai dari sini adalah konstruksi – mari kita mulai… 

Membangun graf sederhana

Langkah 1: Definisikan masalah. 

Misalkan kita ingin memodelkan jaringan kecil pertemanan dalam sebuah jejaring sosial. 

Kita dapat menggunakan pustaka NetworkX di Python, yang dibuat untuk analisis jaringan, untuk memodelkannya. 

Mari mulai dengan membuat sebuah graf: 

# Import libraries 
import networkx as nx # Network analysis
import matplotlib.pyplot as plt # Data visualization
import pydot # Python interface to Graphviz
from networkx.drawing.nx_pydot import graphviz_layout
# Create a graph
graph = nx.Graph() 

Langkah 2: Identifikasi simpul. 

Dalam jejaring sosial fiksi kita, ada empat individu: Alice, Bob, Carol, dan Dave. Individu-individu ini akan direpresentasikan sebagai simpul dalam graf kita – ingat, ini mewakili entitas atau lokasi dalam struktur yang dimodelkan.

Berikut cara kita membuat simpul di Python:

# Add the nodes 
# graph.add_node("Alice") --> Add one node per time
graph.add_nodes_from([
    "Alice","Bob", "Carol", "Dave"
]) # Add multiple nodes

Langkah 3: Tentukan sisi. 

Misalkan koneksi pertemanan adalah sebagai berikut:

• Alice berteman dengan Bob dan Carol.
• Bob berteman dengan Alice dan Dave.
• Carol berteman dengan Alice.
• Dave berteman dengan Bob.

Artinya hubungan-hubungan ini membentuk sisi:

• Alice-Bob
• Alice-Carol
• Bob-Dave

Berikut cara kita mendefinisikan sisi di Python: 

# Add the edges
# graph.add_edge("Alice", "Bob") --> Add one edge per time
graph.add_edges_from([("Alice", "Bob"), 
                      ("Alice", "Carol"),
                      ("Bob", "Dave"),
                      ("Bob", "Alice")  # Ensuring all described edges are included
                     ]) # Add multiple edges

Langkah 4: Gambar graf.

Setelah simpul dan sisi didefinisikan, kita dapat menggambar graf untuk memvisualisasikan hubungan. Potongan kode di bawah ini akan membuat representasi grafis dari jaringan dengan simpul dan sisi berlabel:

# Visualize the plot
pos = graphviz_layout(graph, prog="dot")
nx.draw(graph, 
        pos, 
        with_labels=True, 
        node_size=1000, 
        node_color=["pink", "yellow", "tan", "orange"])
plt.show()

Keluaran: Ini akan menghasilkan graf yang menunjukkan koneksi antara Alice, Bob, Carol, dan Dave seperti yang dijelaskan.

Kode ini menghasilkan graf berikut: 

Graf sederhana yang memodelkan jejaring sosial [dibuat oleh penulis]

Jika Anda ingin memodelkan jejaring sosial Anda sendiri, salin DataLab Notebook ini dan lakukan perubahan sesuai kebutuhan. 

Menganalisis Graf Sederhana

Langkah 1: Periksa keterhubungan. 

Karena kita dapat menelusuri dari simpul mana pun ke simpul lainnya melalui rangkaian sisi, graf ini terhubung. 

Untuk memahaminya lebih baik, berikut jalur antara setiap pasangan simpul: 

• Alice ke Bob: Sisi langsung.
• Alice ke Carol: Sisi langsung.
• Alice ke Dave: Melalui Bob.
• Bob ke Carol: Melalui Alice.
• Bob ke Dave: Sisi langsung.
• Carol ke Dave: Melalui Alice dan Bob.

Langkah 2: Tentukan derajat tiap simpul. 

Ingat, kita mendefinisikan derajat simpul sebagai “jumlah sisi yang terhubung dengannya.” Menerapkan pengetahuan ini pada contoh kita, kita akan menemukan: 

• Alice = derajat 2 (terhubung ke Bob dan Carol)
• Bob = derajat 2 (terhubung ke Alice dan Dave)
• Carol = derajat 1 (terhubung ke Alice)
• Dave = derajat 1 (terhubung ke Bob)

Setiap derajat ditentukan dengan menghitung jumlah sisi yang terkait dengan setiap simpul, berdasarkan hubungan pertemanan yang diberikan.

Langkah 3: Identifikasi jalur dan siklus.

Sebuah jalur antara Alice dan Dave dapat berupa Alice → Bob → Dave.

Graf ini tidak memiliki siklus, karena tidak ada jalur yang kembali ke simpul awal tanpa mengulang langkah.

Langkah 4: Temukan sentralitas.

Alice dan Bob adalah yang paling sentral dalam jaringan ini, karena masing-masing terhubung ke tiga simpul lainnya. Carol dan Dave kurang sentral, masing-masing hanya terhubung ke satu simpul lain.

Kesimpulan

Teori graf menyediakan kerangka kerja yang kuat untuk menelaah dan menyelesaikan hubungan serta struktur kompleks yang ditemukan di berbagai bidang. Dengan memahami konsep inti seperti simpul, sisi, dan berbagai jenis graf, serta mengeksplorasi penerapan praktisnya, Anda dapat memperoleh wawasan berharga untuk mengoptimalkan sistem dan menyelesaikan masalah dunia nyata.

Saat Anda terus mengeksplorasi teori graf, ingatlah bahwa prinsip-prinsipnya tidak hanya bersifat teoretis—prinsip-prinsip tersebut penting untuk menghadapi tantangan dunia nyata, meningkatkan konektivitas, dan meningkatkan efisiensi sistem. Pemahaman yang kuat tentang teori graf akan meningkatkan keterampilan pemecahan masalah Anda dan memberi perspektif lebih dalam tentang sistem-sistem saling terhubung di sekitar kita.

Untuk mengembangkan pemahaman Anda tentang teori graf, lihat sumber daya lanjutan berikut yang memperluas materi yang telah kami bahas dalam artikel ini: 

• Pengantar Komprehensif Graph Neural Networks (GNN)
• Optimasi Graf dengan NetworkX di Python
• Tutorial Klasifikasi Pohon Keputusan di Python