Please enable JavaScript.
Coggle requires JavaScript to display documents.
Chương 1: Đại cương về đồ thị : - Coggle Diagram
Chương 1: Đại cương về đồ thị
:
Các định nghĩa & khái niệm cơ bản
Đồ thị có hướng
G = (V, E) với V là tập hợp các đỉnh của đồ thị, E là tập hợp các cung của đồ thị
Cung e = (i, j) là cung chỉ đi từ i đến j
Các loại đồ thị có hướng: đơn đồ thị, đa đồ thị, giả đồ thị
Đồ thị vô hướng
G = (V, E) với V là tập hợp các đỉnh của đồ thị, E là tập hợp các cung của đồ thị
Cung e = (i, j) là cung đi từ i đến j cũng đồng nghĩa với cung đi từ j đến i
Các loại đồ thị vô hướng: đơn đồ thị, đa đồ thị, giả đồ thị
Các khái niệm khác
Khuyên: cung có gốc và ngọn trùng nhau
Đỉnh kề: là 2 đỉnh có chung cung
Cung kề: là 2 cung có chung 1 đỉnh
Bậc của 1 đỉnh: tổng bậc vào & bậc ra của đỉnh đó hoặc là số cung chứa với đỉnh đó
Bậc của đồ thị = tổng bậc các đỉnh = số cung x2
Biểu diễn đồ thị
Danh sách cung
Lưu giữ các cung của đồ thị trong 1 danh sách hoặc mảng
Có thể lưu được đa cung
Mỗi cung sẽ được biểu diễn với 2 số nguyên tương ứng với 2 đỉnh của 1 cung
Đối với đồ thị vô hướng, trong danh sách tồn tại cung (u, v) tức cũng tồn tại cung (v, u) & ngược lại. Chỉ cần lưu trữ 1 trong 2
Danh sách đỉnh kề
Với mỗi đỉnh, ta lưu các đỉnh kề với nó vào trong 1 danh sách
Nếu đồ thị không có đa cung thì danh sách đỉnh kề sẽ không có phần tử nào trùng nhau. Nếu đồ thị có chứa đa cung thì ngược lại
Ma trận đỉnh - đỉnh
Có dạng ma trận n.n với n là số đỉnh
Đối với đơn đồ thị, phần tử tại vị trí i j có giá trị là 1 nếu đỉnh i kề với đỉnh j. Ngược lại là 0
Đối với đa đồ thị, phần tử tại vị trí i j có giá trị là số lượng cung đi từ đỉnh i đến đỉnh j nếu đỉnh i kề với đỉnh j. Ngược lại là 0
Nếu đồ thị có chứa khuyên, phần tử tại vị trí i i sẽ có giá trị là số khuyên tại đỉnh i
Ma trận đỉnh - cung
Có dạng ma trận n.m với n là số đỉnh, m là số cung
Đối với đồ thị vô hướng, phần tử tại vị trí v, e có giá trị là 1 nếu đỉnh v liên thuộc với cung e, ngược lại là 0
Đối đồ thị có hướng, phần tử tại vị trí v, e có giá trị là +1 nếu đỉnh v là đỉnh gốc của cung e, có giá trị là -1 nếu đỉnh v là đỉnh ngọn của cung e, giá trị là 0 nếu đỉnh v không liên thuộc với đỉnh e