Rangkaian dalam Teori Graf

Teori graf menggunakan beberapa istilah asas untuk menerangkan struktur rangkaian.

• Graf — gambar rajah yang terdiri daripada bucu (vertex) yang disambungkan oleh tepi (edge).
• Rangkaian — graf yang mempunyai sekurang-kurangnya sepasang bucu yang berkait.
• Darjah bagi sesuatu bucu — bilangan tepi yang bersambung dengannya; contohnya jika 3 garis bersambung ke satu bucu, darjahnya ialah 3.

Graf boleh dikategorikan mengikut ciri arah, nilai dan struktur.

• Graf terarah — mempunyai anak panah menunjukkan arah pergerakan (contoh: jalan sehala).
• Graf tak terarah — boleh dilalui dari kedua-dua arah.
• Graf berpemberat — mempunyai nilai (seperti jarak atau kos) pada setiap tepi.
• Pokok — rangkaian yang menyambungkan semua bucu tanpa membentuk sebarang gelung; jika ada n bucu, pokok mempunyai tepat n−1 tepi.

Hasil tambah darjah semua bucu dalam sesuatu graf ialah dua kali bilangan tepinya, iaitu ∑d(V) = 2E, kerana setiap tepi mempunyai dua hujung.

• Gelung — tepi yang bermula dan berakhir pada bucu yang sama; ia menyumbang 2 kepada darjah bucu itu.
• Tepi berbilang — dua atau lebih tepi yang menyambungkan pasangan bucu yang sama.
• Graf mudah — graf tidak terarah tanpa gelung dan tanpa tepi berbilang.
• Akibat rumus darjah — oleh sebab ∑d(V) sentiasa genap, bilangan bucu yang berdarjah ganjil dalam sesuatu graf sentiasa genap.
• Subgraf — graf yang semua bucu dan tepinya diambil daripada graf asal.
• Pokok — graf mudah yang terkait dan tidak mempunyai sebarang kitaran; pokok dengan V bucu mempunyai tepat V − 1 tepi.
• Graf berpemberat — pemberat pada tepi boleh mewakili jarak, masa atau kos. Laluan terbaik ialah laluan dengan jumlah pemberat paling kecil, bukan semestinya laluan dengan paling sedikit tepi.
• Graf terarah — sesuai untuk memodelkan jalan sehala, carta alir sesuatu proses atau hubungan mengikuti akaun di media sosial.

Rangkaian digunakan untuk memodelkan sistem pengangkutan awam, rangkaian jalan raya, rangkaian elektrik, rangkaian sosial dan susun atur laluan di dalam bangunan.

Kebanyakan soalan rangkaian boleh disemak dengan rumus ∑d(V) = 2E.

• Gelung dikira darjah 1 — salah; setiap gelung menambah 2 kepada darjah bucunya.
• Graf terarah dianggap dua hala — ikut arah anak panah apabila mencari laluan.
• Pokok yang tidak lengkap — pokok mesti menyambungkan semua bucu; jika ada bucu terasing, ia bukan pokok bagi graf itu.
• Memilih laluan paling sedikit tepi — dalam graf berpemberat, jumlahkan pemberat setiap laluan yang mungkin sebelum memilih.