Graphs/Networks

Loading Web-Font TeX/Math/Italic

Forward

Graphs/Networks
An Introduction

Prof. David Bernstein
James Madison University

Computer Science Department

bernstdh@jmu.edu

Print

Notation

Back

Forward

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:

General and Directed Graphs

Back

Forward

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

Back

Forward

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.)

Back

Forward

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}$

MathJax Math Υ 