Graphs/Networks

JMU

Graphs/Networks
An Introduction

Prof. David Bernstein
James Madison University

Computer Science Department

bernstdh@jmu.edu

Notation

Getting Started:
- \(V\) is a non-empty, finite set of vertices (or nodes)
- \(L\) is a finite set of unordered pairs of distinct elements of \(V\) called links (or edges or arcs)
- A link \({v,w}\) is said to join the vertices \(v\) and \(w\)
Graphs:
- A simple graph, \(G\), is an ordered pair \((V,L)\)
Visualization:

Simple Graphs

Observations:
- There can never be more than one link joining any two vertices in a simple graph.
- Since links can only join distinct vertices, simple graphs cannot contain loops
Visualization:

General and Directed Graphs

General Graph:
- A general graph (or simply a graph) can contain multiple links between two vertices and loops
Directed Graph:
- In a directed graph (or digraph) the link-set contains ordered pairs of elements of \(V\)

Terminology

Vertices and Links:
- Two vertices, \(v\) and \(w\), are said to be adjacent if there is a link joining them, and the two vertices are then said to be incident to such a link
- The degree (or valency) of a vertex, \(v\), is the number of links incident to it
- Any vertex of degree 0 is said to be isolated
- Any vertex of degree 1 is said to be an end-vertex
Visualization:

Terminology (cont.)

A Walk:
- A finite sequence of arcs of the form \((v_{0}, v_{1}), (v_{1}, v_{2}), ... , (v_{k-1}, v_{k})\)
- \(v_{0}\) is referred to as the initial vertex and \(v_{k}\) is referred to as the final vertex
A Trail:
- A walk in which all of the arcs are distinct
A Path (or Route):
- A trail in which all of the vertices are distinct
A Tour (or Circuit):
- A path in which \(v_{0} = v_{k}\)

Terminology (cont.)

Graphs:
- A graph whose link-set is empty is called a null graph (or a totally-disconnected graph)
- A simple graph in which every pair of distinct vertices are adjacent is called a complete graph
- A graph in which every vertex has the same degree is called a regular graph
- A graph which contains no tours/circuits is said to be a forest
- A connected forest is called a tree
- A spanning tree of a graph is a partial graph (i.e., another graph with the same number of vertices) that forms a tree
Visualization: