Apa itu Graph?

Graph adalah kumpulan titik (disebut vertex atau simpul) dan garis yang menghubungkan titik-titik tersebut (disebut edge atau sisi). Graph digunakan untuk memodelkan hubungan antar objek, misalnya:

Jaringan sosial (hubungan pertemanan)
Jaringan komputer
Peta jalan

Definisi Subgraph

Subgraph adalah bagian dari graph yang terdiri dari beberapa simpul dan sisi dari graph aslinya. Artinya, subgraph mengambil sebagian titik dan/atau sisi dari graph utama.

Contoh: Jika graph G punya 5 simpul dan 7 sisi, maka subgraph H bisa saja hanya terdiri dari 3 simpul dan 2 sisi dari G.

Secara formal: H adalah subgraph dari G jika V(H) ⊆ V(G) dan E(H) ⊆ E(G).

Jenis-jenis Subgraph

1. Spanning Subgraph (Subgraph Rentang)

Spanning subgraph adalah subgraph yang memuat semua simpul dari graph asli, tetapi hanya sebagian sisi saja.

Ciri-ciri:

Semua simpul dari graph utama tetap ada
Sisi boleh berkurang

Contoh: Jika graph G punya 5 simpul dan 7 sisi, spanning subgraph H akan punya 5 simpul dan bisa saja hanya 4 sisi.

Rumus: V(H) = V(G) dan E(H) ⊆ E(G)

2. Vertex-Induced Subgraph (Subgraph Terinduksi Simpul)

Vertex-induced subgraph adalah subgraph yang dibentuk dari memilih beberapa simpul, lalu mengambil semua sisi yang menghubungkan simpul-simpul tersebut di graph asli.

Ciri-ciri:

Pilih beberapa simpul dari graph utama
Semua sisi yang menghubungkan simpul-simpul itu juga diambil

Contoh: Jika dipilih simpul A, B, dan C, maka semua sisi yang menghubungkan A-B, B-C, atau A-C di graph utama akan masuk ke subgraph.

Rumus: H = G[S], S adalah himpunan simpul terpilih

3. Edge-Induced Subgraph (Subgraph Terinduksi Sisi)

Edge-induced subgraph adalah subgraph yang dibentuk dari memilih beberapa sisi, lalu mengambil semua simpul yang terhubung oleh sisi-sisi tersebut.

Ciri-ciri:

Pilih beberapa sisi dari graph utama
Semua simpul yang terhubung oleh sisi-sisi itu juga diambil

Contoh: Jika dipilih sisi AB dan BC, maka simpul A, B, dan C akan masuk ke subgraph.

Rumus: H = G[X], X adalah himpunan sisi terpilih

Apa itu Path?

Path adalah urutan simpul yang saling terhubung melalui sisi.

Jenis Path:

Simple Path: Tidak ada simpul yang berulang
Cycle: Path yang kembali ke simpul awal

Path sering digunakan untuk mencari rute terpendek, mendeteksi siklus, dan lain-lain.

Apa itu Konektivitas (Connectivity)?

Konektivitas adalah sifat sebuah graph apakah semua simpulnya saling terhubung atau tidak.

Jenis:

Connected Graph: Setiap pasangan simpul ada path-nya
Disconnected Graph: Ada simpul yang tidak terhubung ke simpul lain

Kesimpulan

Graph: Struktur dasar matematika untuk relasi
Subgraph: Bagian dari graph utama
Path: Urutan simpul yang terhubung
Konektivitas: Apakah graph menyatu atau terpisah

Kalkulator Simulasi Graph dan Subgraph