Sandbox:DavidKohler/Relativized Alon Conjecture/Directed graph
In our work, a directed graph is the most fundamental object. Our notion of graph is built upon it.
Definition
A directed graph or digraph is a tuple G = (VG, EG, tG, hG) where VG and EG are disjoint sets and tG and hG are maps:
- VG is called the vertex set and its elements are the vertices,
- EG is called the (directed) edge set and its elements are the edges,
- tG: EG → VG is the tail map and
- hG: EG → VG is the head map.
Example
To do.
Basic terminology
- The tail of a directed edge e is the vertex tG(e),
- The head of a directed edge e is the vertex hG(e),
- A directed edge e is called a self-loop if its tail and head are the same vertex.
Morphisms
Let G and H be two directed graphs, a morphism of directed graph φ: G → H is a pair (φV, φE) where φV: VG → VH is a map of vertices and φE: EG → EH is a map of edges satisfying
- hH φE = φV hG
- tH φE = φV tG
With this notion of morphisms, directed graphs form a category.
Adjacency
The head and tail vertices of an edge are said to be adjacent. Adjacency relationships in a graph are captured by an adjacency matrix. Given an ordering {v1, ..., vn} of the vertices, the corresponding adjacency matrix is the n×n matrix AG whose i, j coefficient is the number of directed edges e whose tail is the vertex vi and whose head is the vertex vj.
The eigenvalues of the adjacency matrix, which are independent of the choice of an ordering of the vertices, are called the graph eigenvalues and are one of the main object of study of this work.
In the litterature
As can be seen on Wikipedia, there are several variations on the definitions of graphs. For some authors, our definition is a multigraph or a pseudograph (some allow loops, some do not). In our language, what is commonly referred to as a graph is a simple undirected graph.
Also quivers.