Phenquestions
A node in a graph is called a vertex (plural - vertices). It is sometimes still called a node; it can also be called a point. A link in a graph is called an edge. It is sometimes still called a link; it can also be called a line.
Graph with many Features
This figure shows a graph with many features:
The circles (disks) are vertices. Any straight line or curved line or loop is an edge.
Features of the Graph
Vertex
A vertex is an object. It can be a house; it can be a person; it can be an abstract noun; it can be any object you can think of.
Edge
An edge is a connection (relation) between two vertices; the connection may be abstract.
Loop
A loop is an edge that connects a vertex to itself.
Arrow Edge
Consider two people: John and Peter. If John lends Peter $100, and if John and Peter are vertices, then the lending edge will be pointing towards Peter. If both partners forget that Peter is owing John, and Peter lends John $100, then at the other end of the same edge, an arrowhead will be pointing towards John. If Peter lent but $75 to John and not $100, then a different edge would connect Peter to John. This second edge will have its arrowhead pointing towards John. In the second case, there are two edges, with one arrowhead each, pointing in opposite directions.
The vertex to which an edge points, is a head vertex for that edge. The vertex from which an edge leaves, is a tail vertex.
Incident
An edge connects two vertices. The edge is said to be incident on either vertex. The edge does not need to have an arrowhead. The two vertices are known as the endpoints of the edge. It is possible to have a graph where a vertex does not belong to any edge, but that will not be considered in this tutorial.
Undirected Graph
An edge can be an arrow, or it cannot. A graph where no edge is an arrow is an undirected graph. An edge can be represented by a straight line or a curve or a loop.
Directed Graph
A graph where each edge is an arrow (direction) is a directed graph. An arrow edge can be represented by a straight line with an arrowhead or a curve with an arrowhead or a loop with an arrowhead.
The absence of a direction on the edge of an undirected graph, means each edge of the undirected graph, is bidirectional.
Degree of a Vertex
The number of edges that are incident on a vertex is the degree of the vertex. A loop has two incidences on a vertex, so a loop is counted two times.
Order of a Graph
The order of a graph is the number of vertices in the graph.
Multigraph
A multigraph is a graph, where for some pairs of vertices, there are more than one edges. An undirected multigraph is such a graph in which the edges have no directions (are not arrows). A directed multigraph is one where each edge is an arrow, and for pairs of vertices that have more than one arrow, one vertex is the tail of those arrows, and the other vertex is the head of the same arrows. The following diagram shows an undirected multigraph:
More than one edges (i.e. multiple edges) for a pair of vertices are also called parallel edges.
Quiver
A quiver is a multigraph that allows loops (one or more loops). Some multigraphs do not allow loops.
Simple Graph
A simple graph is a graph where no two pairs of vertices have multiple edges. Loops are not allowed in a simple graph.
Empty Graph
An empty graph is a graph with no vertices and so no edges.
Mixed Graph
A mixed graph is a graph where some edges are arrows, and others are not; in other words: some edges have directions, and others are not directed.
Weighted Graph
It is possible to have a graph in which a number, known as weight, is assigned to each edge. Some edges have the same number, but the numbers are generally different. Such a graph is called a weighted graph. The numbers for a particular graph may represent lengths or costs (prices) or magnitude of some sort, depending on the problem.
Indegree and Outdegree
The vocabulary, indegree, and outdegree are applicable to a directed graph only. The graph may or may not be a multigraph. The graph may or may not have loops.
The number of arrowheads connected to a vertex is the indegree of that vertex. An arrow with a single arrowhead has a head end and a tail end. The number of tails connected to a vertex is the outdegree of that vertex.
Note: A graph with multiple edges for the pair of vertices, where the multiple edges are in opposite directions, is not addressed in this tutorial.
Software Representation of a Graph
A graph can be represented in software the way it is drawn on the diagram. A graph can also be represented in software by a mathematical matrix (two-dimensional array). One of such matrices is called adjacency matrix.
Adjacency Matrix
An adjacency matrix is a square matrix. The headings for the rows are all the vertices, written in ascending order. The headings for the columns are still the same vertices, written in ascending order. Counting of the rows or columns of a matrix begins from 1 and not zero as with arrays. When identifying an element in a matrix, the row number is written first before the column number.
For an undirected graph, each entry (element) in the adjacency matrix is the number of edges connecting the two corresponding vertices. A loop should be counted twice. For a directed graph, each entry in the adjacency matrix is either the number of edges leaving a row vertex and entering the corresponding column vertex or is the number of edges leaving a column vertex and entering the corresponding row vertex. The choice is that of the programmer. In this situation (either case), a loop should still be counted once.
Note: A graph is a diagram is a data structure in its own right. An adjacency matrix is also a data structure in its own right.
Undirected Graph and Adjacency Matrix
The following diagrams show an undirected graph and the corresponding adjacency matrix:
The leading diagonal of a matrix is the diagonal from top-left to bottom-right. An undirected matrix is symmetrical about the leading diagonal. The matrix entry for row A and column C is 1, meaning that there is one edge connecting vertex A and vertex C. The matrix entry for row C and column B is 3, meaning there are 3 edges connecting vertex C and vertex B. The other entries are similarly explained.
The sum of the entries for a row gives the number of edges (degree) for the corresponding vertex. The sum of the entries for row A is 2, meaning 2 edges are connected to vertex A. The sum of the entries for row B is 6, meaning 6 edges are connected to vertex B. The rest of the entries are similarly explained.
Directed Graph and Adjacency Matrix
The following diagrams show a directed graph and the corresponding adjacency matrix:
The adjacency matrix for a directed graph is not necessarily symmetrical about the leading diagonal. The matrix entry for row A and column C is 1, meaning that one edge leaves from vertex A to vertex C. The matrix entry for row C and column B is 3, meaning 3 edges leave from vertex C to vertex B. The other entries are similarly explained.
The sum of the entries for a column gives the indegree for the (column) vertex. The sum of the entries for a row gives the outdegree for the (row) vertex. The sum of the entries for column A is 1, meaning one edge is directed to vertex A. The sum of the entries for row B is 2, meaning 2 edges leave from vertex B. The rest of the entries are similarly explained.
Graph Operations
A data structure, such as a graph, consists of a set of data values or a set of objects, plus the relationship between the objects, plus the operations (functions) between the objects. The relationships in a graph are indicated by the edges. On to that, a graph should have at least the following operations:
adjacent(G, x, y)
G means graph. This operation verifies whether an edge connects vertex x and vertex y. The value and position of an entry in a matrix indicate the connection of an edge (and its type).
neighbors(G, x)
This operation returns a list of all the vertices that are directly connected to the vertex x. The value and position of an entry in a matrix indicate the connection of an edge.
remove_vertex(G, x)
This operation removes a vertex, x from a graph. If the vertex had no edge, there is no problem. However, if the vertex had links, then the links (edges) should be removed as well. The value and position of an entry in a matrix indicate the presence of a particular vertex. If a vertex is removed, the matrix has to be readjusted.
add_vertex(G, x)
This adds a vertex, x without adding edges, or replaces a vertex that had edges but had been removed. The value and position of an entry in a matrix indicate the presence of a particular vertex. If a vertex is added, the matrix has to be readjusted.
add_edge(G, x, y)
This operation adds a new edge between the vertex x and the vertex y if the edge was not there. The value and position of an entry in a matrix indicate the presence of a particular edge. If an edge is added, the matrix has to be readjusted.
remove_edge(G, x, y)
This operation would remove the edge between the vertex x and the vertex y if the edge were there. The value and position of an entry in a matrix indicate the presence of a particular edge. If an edge is removed, the matrix has to be readjusted.
get_vertex_value(G, x)
This operation returns the value, v associated with the vertex, x. To achieve this, you need a power set of subsets for vertex labels and their values.
set_vertex_value(G, x, v)
This operation gives a new value, v for the value associated with the vertex, x. To achieve this, you need a power set of subsets for vertex labels and their values.
Some graphs associate values to their edges as well. Such graphs need the following additional operations:
get_edge_value(G, x, y)
This operation returns the value, v associated with the edge, (x, y). To achieve this, you need a power set of subsets for edges and their values.
set_edge_value(G, x, y, v)
This operation gives a new value, v for the value associated with the edge, (x, y). To achieve this, you need a power set of subsets for edges and their values.
Conclusion
A graph is a set of vertices connected with edges. A graph can be undirected or directed. The edges may be un-directional or directional. Loops may be present or absent in a graph. What you should learn next is set, power set, and multiset related to graphs. After that, you should learn the different types of graphs, such as an oriented graph, regular graph, complete graph, bipartite graph, tournament graph, flow network graph, etc.
Chrys
About the author
Chrysanthus Forcha
Discoverer of mathematics Integration from First Principles and related series. Master's Degree in Technical Education, specializing in Electronics and Computer Software. BSc Electronics. I also have knowledge and experience at the Master's level in Computing and Telecommunications. Out of 20,000 writers, I was the 37th best writer at devarticles.com. I have been working in these fields for more than 10 years.
View all posts
