Máy Tính Ma Trận Kề

Chuyển đổi giữa ma trận kề, danh sách cạnh và danh sách kề. Tự động phát hiện đồ thị có hướng/vô hướng, tính toán dãy bậc, mật độ, các thành phần liên thông và lũy thừa ma trận — với trực quan hóa đồ thị SVG tương tác.

Máy Tính Ma Trận Kề

Ví dụ nhanh:

Tam giác + đuôi vô hướng Chu trình có hướng K4 (danh sách kề) Ma trận 4×4 Nhãn số

↔ Danh sách cạnh ☰ Danh sách kề ▦ Ma trận kề

Dữ liệu đồ thị

Chấp nhận A-B, A->B, A B, A,B, hoặc các hàng ma trận như 0 1 1 0. Sử dụng chữ cái, chữ số hoặc dấu gạch dưới cho nhãn đỉnh.

Nhãn ma trận (tùy chọn)

Các nhãn cách nhau bởi dấu phẩy hoặc dấu cách, mỗi nhãn cho một hàng ma trận. Mặc định là A, B, C… nếu bỏ trống.

Loại đồ thị

Embed Máy Tính Ma Trận Kề Widget

Giới thiệu về Máy Tính Ma Trận Kề

Máy tính Ma trận kề là một công cụ lý thuyết đồ thị giúp chuyển đổi giữa ba biểu diễn đồ thị chuẩn — ma trận kề, danh sách cạnh và danh sách kề — đồng thời bổ sung kết quả với phân tích cấu trúc: dãy bậc, mật độ đồ thị, các thành phần liên thông và lũy thừa ma trận. Nó tự động phát hiện xem đầu vào của bạn mô tả đồ thị có hướng hay vô hướng và hiển thị hình ảnh hóa SVG trực tiếp bên cạnh mỗi kết quả.

Ma trận kề là gì?

Cho một đồ thị G = (V, E) có n đỉnh, ma trận kề của nó là ma trận vuông n × n A có mục nhập A[i][j] bằng 1 nếu có một cạnh từ đỉnh i đến đỉnh j, và 0 nếu ngược lại.

A[i][j] = 1 nếu (v_i, v_j) ∈ E , ngược lại 0

Đối với đồ thị vô hướng, ma trận kề luôn đối xứng: mỗi cạnh {u, v} đóng góp cả A[u][v] = 1 và A[v][u] = 1. Đối với đồ thị có hướng (digraph), ma trận có thể không đối xứng, phản ánh hướng của mỗi cung.

Ba biểu diễn — Chọn biểu diễn phù hợp với vấn đề của bạn

Biểu diễn	Không gian	Tra cứu cạnh	Liệt kê hàng xóm	Tốt nhất cho
Ma trận kề	Θ(n²)	O(1)	Θ(n)	Đồ thị dày; đại số ma trận (lũy thừa, giá trị riêng)
Danh sách kề	Θ(n + m)	O(deg v)	Θ(deg v)	Đồ thị thưa; thuật toán BFS/DFS và đường đi ngắn nhất
Danh sách cạnh	Θ(m)	Θ(m)	Θ(m)	Đầu vào/đầu ra, thuật toán Kruskal tìm MST, các thuật toán tập trung vào cạnh

Các thông số chính được tính toán

Dãy bậc

Đối với đồ thị vô hướng, bậc của một đỉnh là số lượng cạnh liên thuộc với nó (với các khuyên được tính hai lần). Đối với đồ thị có hướng, mỗi đỉnh có một bậc vào (các cung đi vào) và bậc ra (các cung đi ra). Danh sách các bậc được sắp xếp là một bất biến đồ thị cổ điển được sử dụng trong kiểm tra đẳng cấu và định lý khả thi Erdős–Gallai.

Bổ đề bắt tay: Σ deg(v) = 2m (vô hướng) Σ in-deg(v) = Σ out-deg(v) = m (có hướng)

Mật độ đồ thị

Mật độ đo lường mức độ "đầy" của một đồ thị so với số lượng cạnh tối đa có thể có trên n đỉnh.

Vô hướng: D = 2m / (n(n−1)) Có hướng: D = m / (n(n−1))

Mật độ bằng 0 nghĩa là không có cạnh, 1 nghĩa là đồ thị đầy đủ, và các giá trị dưới 0.1 thường chỉ ra một đồ thị thưa, nơi mà danh sách kề sẽ tiết kiệm không gian hơn so với ma trận.

Thành phần liên thông

Một thành phần liên thông là một tập con tối đại của các đỉnh sao cho mọi cặp đều được nối với nhau bằng một đường đi. Đối với đồ thị có hướng, máy tính này báo cáo các thành phần liên thông yếu (bỏ qua hướng mũi tên) — chính là các tập con bạn sẽ nhận được bằng cách coi mỗi cung là một cạnh vô hướng.

Lũy thừa ma trận (A², A³ ... )

Một định lý cơ bản của lý thuyết đồ thị đại số phát biểu rằng mục nhập (i, j) của A^k bằng số lượng đường đi có độ dài chính xác là k từ đỉnh i đến đỉnh j. Do đó:

A²[i][i] bằng bậc của đỉnh i (vô hướng), vì một đường đi 2 bước từ i về chính nó là "đi đến một hàng xóm và quay lại".
Vết (trace) của A³ chia cho 6 đếm số lượng tam giác trong đồ thị vô hướng.
Việc Aⁿ⁻¹ có bất kỳ mục nhập nào bằng không hay không sẽ cho bạn biết liệu đồ thị có liên thông hay không.

Các định dạng đầu vào được chấp nhận

1. Danh sách cạnh

Mỗi cạnh trên một dòng hoặc cách nhau bởi dấu phẩy. Bất kỳ dấu phân cách nào sau đây đều hoạt động: A-B, A B, A,B, A->B, A--B. Sử dụng -> nếu bạn muốn buộc hiểu theo nghĩa có hướng.

A-B, B-C, C-A, C-D (chu trình 4 vô hướng với một đuôi) A->B, B->C, C->D, D->A (chu trình có hướng độ dài 4)

2. Danh sách kề

Mỗi đỉnh trên một dòng, theo dạng đỉnh: hàng xóm1, hàng xóm2, .... Thứ tự không quan trọng; các đỉnh còn thiếu sẽ được thêm tự động từ danh sách hàng xóm.

A: B, C, D B: A, C C: A, B, D D: A, C

3. Ma trận kề

Mỗi hàng trên một dòng với các giá trị 0/1 cách nhau bởi dấu cách hoặc dấu phẩy. Ma trận phải là ma trận vuông. Tùy chọn cung cấp nhãn tùy chỉnh trong trường Nhãn ma trận (nếu không A, B, C… sẽ được sử dụng).

0 1 1 0 1 0 1 1 1 1 0 1 0 1 1 0

Cách sử dụng Máy tính này

Chọn định dạng đầu vào bằng cách sử dụng bộ chọn tab: danh sách cạnh, danh sách kề hoặc ma trận kề.
Dán hoặc nhập đồ thị của bạn vào vùng văn bản. Đối với đầu vào ma trận, hãy thêm các nhãn tùy chọn trong trường Nhãn ma trận.
Chọn loại đồ thị — để ở chế độ Tự động phát hiện và máy tính sẽ suy ra tính có hướng từ các mũi tên (->) hoặc tính đối xứng của ma trận. Buộc nó thành Có hướng hoặc Vô hướng nếu bạn muốn ghi đè.
Nhấp vào Chuyển đổi & Phân tích đồ thị. Trang kết quả hiển thị ma trận kề, hình ảnh hóa SVG tương tác, hai biểu diễn văn bản còn lại, thống kê bậc, các thành phần liên thông và các ma trận đếm đường đi A² và A³ khi đồ thị đủ nhỏ.
Di chuột qua một hàng ma trận hoặc một nút đồ thị để làm sáng hàng/cột tương ứng và các cạnh liên thuộc — một bằng chứng trực quan tức thì rằng mỗi định dạng đều mã hóa cùng một thông tin.

Ví dụ thực tế

Xét một đồ thị vô hướng trên các đỉnh {A, B, C, D} với các cạnh AB, BC, CA, CD. Ma trận kề là:

A B C D A [ 0 1 1 0 ] B [ 1 0 1 0 ] C [ 1 1 0 1 ] D [ 0 0 1 0 ]

Các sự kiện chính mà máy tính rút ra:

Đối xứng? Có — xác nhận là vô hướng.
Dãy bậc: (3, 2, 2, 1) — đỉnh C là trung tâm.
Mật độ: 2·4 / (4·3) = 0.667 — một đồ thị có mật độ trung bình.
Liên thông? Có, một thành phần duy nhất.
Tam giác: chính xác một (A–B–C), được xác nhận bởi tr(A³) = 6.

Các ứng dụng phổ biến

Phân tích mạng xã hội — đồ thị tình bạn / người theo dõi, tính trung tâm.
Đồ thị Web & trích dẫn — thuật toán PageRank và HITS hoạt động trực tiếp trên A và A^T.
Định tuyến & mạng lưới — đường đi ngắn nhất, lát cắt tối thiểu, luồng tối đa.
Hóa học — đồ thị phân tử với các nguyên tử là đỉnh, liên kết là cạnh.
Lập lịch & giải quyết phụ thuộc — đồ thị có hướng không chu trình (DAGs) trong các hệ thống xây dựng.
Chuỗi Markov — các ma trận ngẫu nhiên theo hàng được dẫn xuất từ đồ thị mã hóa xác suất chuyển trạng thái.

Câu hỏi thường gặp

Ma trận kề là gì?

Ma trận kề là một ma trận vuông n × n được sử dụng để biểu diễn một đồ thị hữu hạn. Mỗi ô A[i][j] là 1 nếu có một cạnh từ đỉnh i đến đỉnh j, và 0 nếu ngược lại. Đối với đồ thị vô hướng, ma trận này đối xứng, do đó A[i][j] = A[j][i]. Ma trận giúp dễ dàng kiểm tra xem hai đỉnh có kết nối với nhau hay không trong thời gian không đổi, và các lũy thừa ma trận mã hóa số lượng đường đi giữa các đỉnh.

Làm thế nào để biết một đồ thị là có hướng từ ma trận kề của nó?

Nếu ma trận kề đối xứng, nghĩa là A[i][j] bằng A[j][i] cho mọi cặp chỉ số, thì đồ thị đó là vô hướng. Nếu có ít nhất một cặp mà A[i][j] khác A[j][i], đồ thị đó là có hướng. Máy tính này thực hiện kiểm tra tính đối xứng đó tự động khi bạn chọn tùy chọn Tự động phát hiện.

Lũy thừa bậc k của một ma trận kề biểu diễn điều gì?

Phần tử (i, j) của A^k đếm số lượng đường đi có độ dài đúng bằng k từ đỉnh i đến đỉnh j. Ví dụ, A²[i][j] là số lượng đường đi 2 bước, tương đương với số lượng hàng xóm chung giữa i và j trong đồ thị vô hướng. Đặc tính này được sử dụng trong các thuật toán đếm tam giác, tính khả đạt và các tính toán kiểu PageRank.

Mật độ đồ thị là gì?

Mật độ đồ thị là tỷ lệ giữa số lượng cạnh hiện có so với số lượng cạnh tối đa có thể có. Đối với một đồ thị đơn vô hướng có n đỉnh, mật độ = 2m / (n(n-1)). Đối với đồ thị có hướng, mật độ = m / (n(n-1)). Mật độ gần bằng 0 nghĩa là đồ thị thưa; mật độ bằng 1 nghĩa là đồ thị đầy đủ.

Ma trận kề khác với danh sách kề như thế nào?

Ma trận kề lưu trữ tính kết nối cho mọi cặp đỉnh bằng n² bit, giúp tra cứu hàng xóm mất O(1) nhưng sử dụng bộ nhớ O(n²). Danh sách kề chỉ lưu trữ các hàng xóm thực tế của mỗi đỉnh, tiêu tốn bộ nhớ O(n + m), nhỏ hơn nhiều đối với đồ thị thưa, nhưng tra cứu hàng xóm yêu cầu quét tuyến tính. Ma trận tốt hơn cho đồ thị dày và các phép toán đại số ma trận; danh sách tốt hơn cho đồ thị thưa và các thuật toán duyệt như BFS/DFS.

Công cụ này có thể xử lý đồ thị có trọng số không?

Máy tính hiện tại tập trung vào các ma trận kề không trọng số với các mục nhập 0/1. Nếu bạn dán một ma trận với các trọng số số khác không, mỗi ô khác không sẽ được coi là 1 để phân tích cấu trúc. Đối với các tính toán đồ thị có trọng số như đường đi ngắn nhất, hãy cân nhắc sử dụng một công cụ đồ thị có trọng số chuyên dụng.

Đọc thêm

Tham khảo nội dung, trang hoặc công cụ này như sau:

"Máy Tính Ma Trận Kề" tại https://MiniWebtool.com/vi/may-tinh-ma-tran-ke/ từ MiniWebtool, https://MiniWebtool.com/

bởi đội ngũ miniwebtool. Cập nhật: 20/04/2026

Bạn cũng có thể thử AI Giải Toán GPT của chúng tôi để giải quyết các vấn đề toán học của bạn thông qua câu hỏi và trả lời bằng ngôn ngữ tự nhiên.

Các công cụ liên quan khác:

Máy tính Dãy số học

Máy tính hệ số nhị thức

Máy tính kết hợp

Máy tính số phức

Máy tính Đường đi Ngắn nhất DijkstraMới

Kiểm tra Số FibonacciMới

Máy Tính Tô Màu Đồ ThịMới

Trình xác thực dãy bậc đồ thịMới

Công cụ Kiểm tra Đường đi HamiltonMới

Máy tính Bao hàm - Loại trừMới

Máy Tính Ma Trận Kề

Giới thiệu về Máy Tính Ma Trận Kề

Ma trận kề là gì?

Ba biểu diễn — Chọn biểu diễn phù hợp với vấn đề của bạn

Các thông số chính được tính toán

Dãy bậc

Mật độ đồ thị

Thành phần liên thông

Lũy thừa ma trận (A², A³ ... )

Các định dạng đầu vào được chấp nhận

1. Danh sách cạnh

2. Danh sách kề

3. Ma trận kề

Cách sử dụng Máy tính này

Ví dụ thực tế

Các ứng dụng phổ biến

Câu hỏi thường gặp

Ma trận kề là gì?

Làm thế nào để biết một đồ thị là có hướng từ ma trận kề của nó?

Lũy thừa bậc k của một ma trận kề biểu diễn điều gì?

Mật độ đồ thị là gì?

Ma trận kề khác với danh sách kề như thế nào?

Công cụ này có thể xử lý đồ thị có trọng số không?

Đọc thêm

Các công cụ liên quan khác:

Phép toán toán học nâng cao:

Công cụ nổi bật: