Adjacency Matrix Generator

Generate adjacency matrices for graphs with visualization. Calculate graph properties and analyze graph structure.

Adjacency Matrix Definition: For a graph with n vertices, the adjacency matrix is an n×n matrix where A[i][j] = 1 (or weight) if there is an edge from vertex i to vertex j, and 0 otherwise.

Performance Notice: Large graphs (>15 vertices) may cause slower calculations. Consider using smaller graphs for optimal performance.
Number of vertices in the graph (2-15 for optimal performance)
Diagonal elements are typically 0 (no self-loops) but can be set for special cases. For undirected graphs, matrix is symmetric.
Complete Graph
Cycle Graph
Star Graph
Path Graph
Empty Graph
Bipartite Graph
Wheel Graph
Random Graph
Random Tree
Generating adjacency matrix and visualization...

Understanding Adjacency Matrices

In graph theory, an adjacency matrix is a square matrix used to represent a finite graph. The elements of the matrix indicate whether pairs of vertices are adjacent or not in the graph.

Mathematical Definition:

For a simple graph with vertex set V = {v₁, v₂, ..., vₙ}, the adjacency matrix is an n×n matrix A where:

A[i][j] = 1 if there is an edge from vᵢ to vⱼ, and 0 otherwise.

For weighted graphs, A[i][j] = w if there is an edge from vᵢ to vⱼ with weight w, and 0 otherwise.

Properties of Adjacency Matrices

Graph Property Matrix Property Example/Explanation
Undirected Graph Symmetric matrix A = Aᵀ (transpose)
No self-loops Zero diagonal A[i][i] = 0 for all i
Degree of vertex i Sum of row i (or column i for undirected) deg(vᵢ) = Σⱼ A[i][j]
Number of walks length k Entries of Aᵏ (Aᵏ)[i][j] = number of walks from i to j of length k
Complete Graph Kₙ All 1's except diagonal A[i][j] = 1 for i≠j, 0 for i=j
Bipartite Graph Block matrix with zero diagonal blocks A = [0 B; Bᵀ 0] (after reordering vertices)
Connected Graph Irreducible matrix No permutation makes it block diagonal
Shortest Path (Floyd-Warshall) Distance matrix D D[i][j] = shortest distance from i to j

Advanced Graph Algorithms

1

Floyd-Warshall Algorithm: Computes shortest paths between all pairs of vertices in weighted graphs. Works with both positive and negative edge weights (no negative cycles). Time complexity: O(n³).

2

Connected Components: For undirected graphs, finds all connected components using DFS/BFS. For directed graphs, finds strongly connected components using Kosaraju's or Tarjan's algorithm.

3

Graph Isomorphism: Checking if two graphs are isomorphic (same structure) is a challenging problem with no known polynomial-time solution for general graphs.

Common Graph Types

  • Complete Graph (Kₙ): Every pair of distinct vertices is connected by a unique edge
  • Cycle Graph (Cₙ): Vertices connected in a closed chain
  • Path Graph (Pₙ): Vertices connected in a single path
  • Star Graph (Sₙ): One central vertex connected to all others
  • Wheel Graph (Wₙ): Cycle graph with an additional central vertex connected to all cycle vertices
  • Bipartite Graph: Vertices can be divided into two disjoint sets with edges only between sets
  • Tree: Connected graph with no cycles
  • Regular Graph: All vertices have the same degree

Advanced Features in This Tool:

  • Shortest Path Calculation: Floyd-Warshall algorithm for all-pairs shortest paths
  • Connectivity Analysis: Find connected components and check graph connectivity
  • Performance Optimized: Uses math.js for efficient matrix operations
  • Four Input Methods: Matrix, edge list, adjacency list, and graph properties
  • Advanced Visualization: Interactive graph with force-directed layout
  • Export Formats: LaTeX, MATLAB, Python, JSON, and GraphML

Frequently Asked Questions

An adjacency matrix is an n×n matrix (n = number of vertices) where entry (i,j) represents the connection between vertices i and j. An incidence matrix is an n×m matrix (m = number of edges) where entry (i,j) indicates whether vertex i is incident to edge j. Adjacency matrices are better for dense graphs, while incidence matrices are more efficient for sparse graphs.

The (i,j) entry of Aᵏ (the k-th power of the adjacency matrix) gives the number of walks of length k from vertex i to vertex j. A walk is a sequence of vertices where each consecutive pair is connected by an edge, and vertices can be repeated. This is useful for analyzing connectivity and distances in graphs.

The Laplacian matrix L of a graph is defined as L = D - A, where D is the degree matrix (diagonal matrix with vertex degrees) and A is the adjacency matrix. For weighted graphs, it's L = D - W where W is the weight matrix. The Laplacian matrix has important applications in spectral graph theory, clustering, and physics (e.g., modeling heat diffusion).

The Floyd-Warshall algorithm is a dynamic programming algorithm that finds shortest paths between all pairs of vertices. It works by considering all vertices as intermediate points. For each pair (i, j), it checks if the path through vertex k is shorter than the currently known path. The algorithm runs in O(n³) time and works with both positive and negative edge weights (as long as there are no negative cycles).

For optimal performance, the tool limits graphs to 15 vertices for matrix input and 30 vertices for edge list input. Larger graphs can be generated but may cause slower calculations. The visualization is optimized for graphs with up to 20 vertices for clarity. For very large graphs, consider using specialized graph analysis software.