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

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ả.

Tóm tắt nhanh

Máy Tính Ma Trận Kề chuyển đổi đồ thị giữa dạng ma trận kề, danh sách cạnh và danh sách kề. Công cụ nhận diện đồ thị có hướng hay vô hướng và báo cáo bậc, mật độ, thành phần liên thông và lũy thừa ma trận.

Máy Tính Ma Trận Kề: tính năng chính

Tính năng	Bạn nhận được	Phù hợp với
Ba định dạng đầu vào	Dán danh sách cạnh như A-B hoặc A->B, danh sách kề như A: B, C, hoặc ma trận vuông 0/1 với nhãn tùy chọn.	Chuyển đồ thị giữa dạng sách giáo khoa và dạng lập trình
Có hướng hoặc vô hướng	Tự nhận diện dựa trên mũi tên và tính đối xứng của ma trận, hoặc bạn có thể buộc Directed hoặc Undirected.	Kiểm tra xem một ma trận có mô tả đồ thị có hướng không
Phân tích bậc	Cho dãy bậc, với bậc vào và bậc ra đối với đồ thị có hướng.	Bài tập lý thuyết đồ thị và kiểm tra dựa trên bậc
Mật độ và thành phần	Báo cáo mật độ đồ thị, đồ thị có đầy đủ, chính quy hay liên thông không, và các thành phần liên thông yếu.	Đánh giá mạng thưa hay kết nối đến đâu
Lũy thừa ma trận	Hiển thị A bình phương và A lập phương, trong đó mỗi phần tử đếm số đường đi có độ dài tương ứng giữa hai đỉnh.	Đếm đường đi và tam giác
Vẽ đồ thị	Sơ đồ tương tác làm nổi bật các hàng, cột và cạnh tương ứng khi rê chuột. Mỗi biểu diễn có thể sao chép.	Thấy ba định dạng cùng mô tả một đồ thị
Giới hạn kích thước	Hỗ trợ đồ thị tối đa 40 đỉnh và 600 cạnh.	Đồ thị nhỏ đến vừa dùng trong lớp học và ví dụ

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.

Đố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

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.

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.

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.

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.

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).

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

1. 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ề.
2. 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.
3. 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 đè.
4. 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ỏ.
5. 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à:

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

• Ma trận kề — Wikipedia

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

• Máy Tính Ma Trận Kề Mới
• Máy Tính Antilog
• Máy tính hàm Beta
• Máy tính hệ số nhị thức
• Máy tính phân phối xác suất nhị thức
• Máy tính Bitwise Phổ biến
• Công Cụ Rút Gọn Đại Số Boolean Mới
• Máy tính Định lý Giới hạn Trung tâm
• Máy tính Định lý Số dư Trung Quốc
• Máy tính kết hợp
• Máy tính hàm lỗi bổ sung
• Máy tính số phức Phổ biến
• Máy tính Phân số liên tục
• Máy tính Hoán vị lệch (Giai thừa phụ)
• Máy tính Đường đi Ngắn nhất Dijkstra
• Máy tính Entropy
• Máy tính chức năng lỗi
• Máy tính Hàm Phi Euler
• Máy tính giảm dần theo cấp số nhân
• Máy tính tăng trưởng theo cấp số nhân
• Máy tính Tích phân Lũy thừa
• Máy Tính Số Mũ (Độ Chính Xác Cao) Phổ biến
• Máy tính Thuật toán Euclid Mở rộng
• Máy tính giai thừa Phổ biến
• Máy tính Hàm Gamma
• Máy tính tỷ lệ vàng
• Máy Tính Tô Màu Đồ Thị Mới
• Trình xác thực dãy bậc đồ thị
• Máy Tính Bậc Lý Thuyết Nhóm Mới
• Máy tính Nửa đời
• Công cụ Kiểm tra Đường đi Hamilton Mới
• Máy tính Bao hàm - Loại trừ Mới
• Công cụ Giải Bản đồ Karnaugh (K-Map) Phổ biến
• Công cụ Giải Quy hoạch Tuyến tính Phổ biến
• Máy tính Phân phối Dừng Chuỗi Markov
• Máy tính Cây khung nhỏ nhất
• Máy Tính Lũy Thừa Modular Mới
• Máy tính Nghịch đảo Nhân theo Mô-đun
• Máy Tính Phân Phối Nhị Thức Âm Mới
• Máy Tính Luồng Mạng (Luồng Cực Đại) Mới
• Máy tính phần trăm tăng trưởng
• Máy tính hoán vị
• Máy tính Hoán vị Có lặp Mới
• Máy tính Nguyên lý Chuồng bồ câu
• Trình Kiểm Tra Đồ Thị Phẳng Mới
• Máy tính Phân phối Poisson
• Máy tính căn bậc của đa thức với các bước chi tiết
• Máy Tính Căn Nguyên Thủy
• Máy tính xác suất
• Máy tính phân bố xác suất
• Máy tính Tỷ lệ thức
• Máy tính công thức bậc hai
• Máy tính Vành và Trường Mới
• Máy Tính Làm Tròn Phổ biến
• Máy Tính Khoa Học
• Máy tính ký hiệu khoa học
• Máy tính lý thuyết tập hợp
• Máy Tính Chữ Số Có Nghĩa Mới
• Trình giải Bài toán Hôn nhân Ổn định Mới
• Máy tính số Stirling
• Máy tính tổng khối
• Máy tính tổng các số liên tiếp
• Máy tính Tổng Bình phương
• Máy Tính Sắp Xếp Topo Mới
• Trình Giải Bài Toán Người Du Hành (TSP) Mới
• Công cụ tạo bảng chân trị
• Công cụ tạo Biểu đồ Venn (3 Tập hợp)