Berikut ini adalah istilah-istilah yang ditemukan dalam teori graf beserta arti/definisinya.
Today Quote
When you look into your mother’s eyes, you know that it is the purest love you can find on this earth.
- Diagram Sirkulasi
Diagram yang dibuat arsitek untuk menganalisis arus pengunjung/mengatur tata letak ruangan dalam gedung besar. - Graf
Pasangan tak berurutan yang terdiri dari himpunan tak kosong berupa himpunan titik/simpul (vertex) dan himpunan boleh kosong berupa himpunan sisi (edge). - Terhubung Langsung/Bertetangga (Adjacent)
Dua buah titik pada graf tak berarah dikatakan terhubung langsung/bertetangga jika kedua titik itu dihubungkan oleh sebuah sisi. - Terkait/Bersisian (Incident)
Untuk sembarang sisi yang menghubungkan dua titik pada graf, sisi itu dikatakan terkait/bersisian dengan dua titik itu. - Sisi Rangkap/Sisi Ganda (Multiple Edges)
Dua sisi atau lebih yang menghubungkan sepasang titik. - Gelang/Kalang (Loop atau Self-Loop atau Buckle)
Sisi yang titik ujungnya sama. - Simpul Terpencil (Isolated Vertex)
Simpul yang tidak memiliki sisi yang bersisian dengannya. - Derajat Simpul (Vertex Degree)
Jumlah sisi yang bersisian/keluar dari simpul. - Graf Trivial (Trivial Graph)
Graf yang hanya memiliki satu titik/simpul (tanpa sisi). - Graf Kosong (Null/Empty Graph)
Graf yang tidak memiliki sisi. Titik/simpulnya bisa lebih dari $1$. - Graf Sederhana (Simple Graph)
Graf yang tidak memuat sisi rangkap maupun gelang (loop). - Graf Tak Sederhana (Unsimple Graph)
Graf yang memuat sisi rangkap atau gelang (loop). - Graf Ganda/Rangkap (Multiple Graph)
Graf yang mengandung sisi rangkap (tidak boleh memuat gelang). - Graf Semu/Graf Palsu/Pseudograf (Pseudograph)
Graf yang mengandung gelang (jika ada sisi rangkap, juga disebut demikian). - Kardinalitas Graf
Jumlah simpul/titik pada graf. - Anting-anting (Pendant Vertex)
Simpul graf yang berderajat $1$. - Graf Tak Berarah (Undirected Graph)
Graf yg sisinya tidak mengandung orientasi arah (berupa garis saja). Dalam hal ini, $(u, v) = (v, u)$ dengan $u$ dan $v$ adalah titik pada graf itu. - Graf Berarah (Directed Graph)
Graf yang sisinya mengandung orientasi arah. Sisinya disebut busur (arc). - Simpul Asal (Initial Vertex) dan Simpul Terminal (Terminal Vertex)
Istilah khusus untuk simpul awal dan simpul akhir pada graf berarah. - Derajat Masuk (In-Degree) dan Derajat Keluar (Out-Degree)
Jumlah busur yang masuk ~ keluar suatu simpul pada graf berarah. - Graf Komplit/Graf Lengkap (Complete Graph)
Graf sederhana dengan setiap pasang titik yang berbeda dihubungkan oleh satu sisi. - Graf Bipartisi (Bipartite Graph)
Graf yang himpunan titiknya dapat dipartisi menjadi $2$ bagian, misalnya $V_1$ dan $V_2$ sedemikian sehingga setiap sisi di dalam $G$ menghubungkan sebuah simpul di $V_1$ ke simpul di $V_2$. - Graf Bipartisi Komplit (Complete Bipartite Graph)
Graf bipartisi dengan himpunan partisi $V_1$ dan $V_2$ yang masing-masing titik di $V_1$ dihubungkan dengan masing-masing titik di $V_2$ oleh TEPAT SATU SISI. - Graf Lingkaran (Circle Graph)
Graf sederhana yang semua simpulnya berderajat dua. - Graf Beraturan-r (Regular-r Graph)
Graf yang semua titiknya berderajat $r$. - Lema Jabat Tangan (Handshaking Lemma)
Jumlah semua derajat simpul pada suatu graf sama dengan 2 kali jumlah sisinya. - Subgraf/Upagraf/Graf Bagian (Subgraph)
Graf yang himpunan titik dan sisinya merupakan himpunan bagian dari graf yang lain. - Subgraf Merentang (Spanning Subgraph)
Subgraf yang mengandung semua titik dari graf induknya. - Vertex Induced Subgraph dari $V_1$
Subgraf $G$ yang himpunan titiknya $V_1$ dan himpunan sisinya beranggotakan semua sisi $G$ yang mempunyai titik ujung di $V_1$. - Edge Induced Subgraph dari $F$
Subgraf $G$ yang himpunan titiknya adalah titik-titik ujung sisi pada $F$ ($F$ adalah himpunan sisi subset dari graf $G$). - Titik Disjoin
Dua subgraf dari graf $G$ yang tidak memiliki titik yang sama. - Sisi Disjoin
Dua subgraf dari graf $G$ yang tidak memiliki sisi yang sama. - Jalan (Walk)
Barisan simpul dan sisi $v_0~e_1~v_1~e_2~\cdots~e_n~v_n$ yang saling terhubung pada suatu graf. - Jalan Trivial (Trivial Walk)
Jalan yang tidak memuat sisi. - Jalan Tertutup (Closed Walk)
Jalan dengan syarat $u = v$ (titik ujungnya sama) dengan $u$ dan $v$ titik pada suatu graf. - Titik Dalam (Internal Vertex)
Titik selain titik ujung pada suatu jalan. - Jalur/Jejak (Trail)
Jalan dengan semua sisinya berbeda. - Lintasan (Path)
Jalan yang semua titiknya berbeda. - Sirkuit (Circuit) atau Trail Tertutup
Jalan tertutup dengan semua sisinya berbeda. - Sikel (Cycle)
Sirkuit yang titik dalamnya berbeda. - Lilitan (girth)
Panjang sikel terpendek pada graf. - Lintasan Euler (Euler Path)
Lintasan yang memuat semua sisi di graf. - Sirkuit Euler (Euler Circuit)
Sirkuit yang memuat semua sisi di graf. - Lintasan Hamilton (Hamiltonian Path)
Lintasan yang melalui tiap simpul di dalam graf tepat satu kali. - Sirkuit Hamilton (Hamiltonian Circuit)
Lintasan Hamilton yang kembali ke titik asal sehingga membentuk lintasan tertutup. - Sikel Hamilton (Hamiltonian Cycle)
Sikel yang memuat semua titik dari suatu graf.
- Graf Hamilton (Hamiltonian Graph)
Graf yang memuat sikel Hamilton. - Graf Lintasan
Graf yang hanya memuat satu lintasan. - Titik Potong (Cut Vertex)
Titik graf terhubung yang bila dihilangkan menyebabkan graf menjadi tidak terhubung. - Jembatan/Sisi Potong(Cut Set/Bridge)
Sisi graf terhubung yang bila dihilangkan menyebabkan graf menjadi tidak terhubung. - Graf Terhubung (Connected Graph)
Graf dengan setiap pasang simpulnya mengandung lintasan. - Graf Berbobot (Weighted Graph)
Graf yang setiap sisinya diberi bobot/nilai. - Matriks Ketertanggaan (Adjacency Matrix)
Matriks yang merepresentasikan banyaknya sisi yang menghubungkan setiap dua simpul dari suatu graf. - Matriks Keterkaitan/Bersisian (Incidency Matrix)
Matriks yang merepresentasikan sisi yang bersisian dengan setiap pasang simpul dari suatu graf. - Daftar/Senarai Ketetanggaan (Adjacency List)
Daftar yang menunjukkan hasil enumerasi simpul yang bertetangga dengan simpul lainnya pada suatu graf. - Pohon (Tree)
Graf terhubung yang tidak memuat sikel. - Graf Planar (Planar Graph)
Graf yang dapat digambar pada bidang datar dengan sisi-sisi yang tidak saling berpotongan. - Graf Bidang (Plane Graph)
Representasi graf planar yang digambarkan dengan sisi-sisinya tidak saling berpotongan.
Jika ada kosa kata atau istilah lain mengenai graf yang tidak tercantum di atas, silakan tambahkan di kolom komentar di bawah.