Discover published sets by community

Explore tens of thousands of sets crafted by our community.

Categories

Mathematics

Graph Theory

Adjacency Matrix vs. Incidence Matrix

Flashcards

0/8

Still learning

A matrix that can be used to determine the number of paths of length $n$ between all pairs of vertices.

By raising an adjacency matrix to the $n^{th}$ power, the resulting matrix elements indicate the number of distinct paths of length $n$ between pairs of vertices in the graph.

A square matrix where entry $a_{ij}$ indicates the number of edges from vertex $i$ to vertex $j$ .

This represents an adjacency matrix of a graph, showing directly which vertices are connected and how many multiple edges there are between them.

In this matrix, each column may have two or more non-zero entries for a graph with hyperedges.

An incidence matrix can represent hypergraphs where an edge can connect more than two vertices, and thus multiple vertices will be incident to such an edge.

A matrix where for each edge $e$ connecting vertices $i$ and $j$ , the entries $e_{i}$ and $e_{j}$ are assigned to 1 and -1 for directed graphs.

This represents a directed graph's incidence matrix, which encodes the direction of each edge by assigning different signs to the vertices at the ends of an edge.

For an undirected graph, this matrix will have 2's on its diagonal if there are loops at every vertex.

In an adjacency matrix, loops are counted twice, hence a loop at vertex $i$ contributes 2 to the diagonal entry $a_{ii}$ . This displays the presence of self-connections within the graph.

A matrix where entry $e_{ij}$ is 1 if vertex $i$ is incident to edge $j$ , otherwise 0.

This describes an incidence matrix, which indicates which vertices are endpoints of a given edge, capturing the connections between edges and vertices.

This matrix is not necessarily square and its dimensions are given by the number of vertices and edges.

The incidence matrix is generally a rectangular matrix because the number of vertices and edges in a graph can be different, reflecting its vertex-edge incidence relationships.

In a directed graph, this matrix shows which vertices have directed paths to others, with possible entries greater than 1.

The adjacency matrix of a directed graph (digraph) indicates the directionality of the graph and allows for multiple edges (parallel paths) by having entries greater than 1.

Know

Still learning

Click to flip

Know