Một đường đi trong G là một dãy luân phiên các đỉnh và cạnh:

$x\_\backslash text\{1\}\; u\_\backslash text\{1\}\; x\_\backslash text\{2\}\; u\_\backslash text\{2\}...x\_\backslash text\{m-1\}\; u\_\backslash text\{m-1\}\; x\_\backslash text\{m\}$ ($x\_\backslash text\{i\}$ là đỉnh và $u\_\backslash text\{i\}$ là cạnh). Trong đồ thị thỏa mãn điều kiện $u\_\backslash text\{i\}$ liên kết với cặp đỉnh $(x\_\backslash text\{i\},\; x\_\backslash text\{i+1\})$, nghĩa là: * $u\_\backslash text\{i\}$ liên kết với $(x\_\backslash text\{i\},\; x\_\backslash text\{i+1\})$ nếu đồ thị có hướng. * $u\_\backslash text\{i\}$ liên kết với $(x\_\backslash text\{i\},\; x\_\backslash text\{i+1\})$ nếu đồ thị vô hướng.

Khi đó ta gọi $x$\text{1} là đỉnh đầu và $x$\text{m} là đỉnh cuối của đường đi.

Ví dụ

*Xét đồ thị G (7 đỉnh) vô hướng sau:* Đồ thị G Dãy các đỉnh: 1 e2 4 e10 5 là một đường đi Đỉnh đầu: 1 * Đỉnh cuối: 5 Dãy các đỉnh: 4 e10 5 e9 3 e12 7 là một đường đi Đỉnh đầu: 4 Đỉnh cuối: 7

Dây chuyền

• Cho đồ thị G=(X, U).
• Một dây chuyền trong đồ thị (G) là một dãy luân phiên các đỉnh và cạnh:

x₁ u₁ x₂ u₂... x_m-1 u_m-11 x_m (x_i là đỉnh và u_i là cạnh)

• Trong đồ thị thỏa mãn điều kiện ui, liên kết với cập đỉnh (xi, xi+1) không phân biệt thứ tự nghĩa là:

u_i =(x_i, x_i+1) hay u_i = (x_i+1, x_i) nếu đồ thị có hướng,

u_i = {x_i, (x_i+1)} nếu đồ thị vô hướng.

• Khi đó ta gọi x₁ là đỉnh đầu và x_m là đỉnh cuối của dây chuyền.

Tính chất "đơn" và "sơ cấp" của đường đi và dây chuyền trong đồ thị

• Tính chất "đơn" của dây chuyền hay đường đi yêu cầu không có cạnh nào xuất hiện hai lần trong dây chuyền hay đường đi đó.
• Tính chất "sơ cấp" (hay cũng gọi là "thứ cấp") yêu cầu không có đỉnh nào xuất hiện hai lần.

Chu trình và Mạch

• Một chu trình trong đồ thị là một dây chuyền đơn mà có đỉnh đầu trùng đỉnh cuối, tức la dây chuyền có dạng: x₁ u₁ x₂ u₂… x_m-1 u_m-1 x_m u_m x₁

sao cho các cạnh u₁, u₂,…,u_m đôi một khác nhau.

• Một mạch trong đồ thị là một đường đi đơn mà có đỉnh đầu trùng đỉnh cuối, tức là đường đi có dạng: x₁ u₁ x₂ u₂… x_m-1 u_m-1 x_m u_m x₁

sao cho các cạnh u₁, u₂,…,u_m đôi một khác nhau. Từ các định nghĩa trên, ta có các khái niệm sau đây thường được dùng trong lý thuyết đồ thị:

Dây chuyền sơ cấp

• Dây chuyền sơ cấp là dây chuyền không có đỉnh lập lại.

Đường đi sơ cấp

• Đường đi sơ cấp là đường đi không có đỉnh lập lại.

Chu trình sơ cấp

• Chu trình sơ cấp là đường đi không có đỉnh lập lại (ngoại trừ đỉnh đầu và đỉnh cuối).

Mạch sơ cấp

• Mạch sơ cấp là mạch không có đỉnh lập lại (ngoại trừ đỉnh đầu và đỉnh cuối).