graph theory terms

Vertices

points on a graph representing an object or entity

edges

lines that connect vertices

loops

an edge that connects a vertex to itself

undirected graph

when you are able to move in either direction along the edges of a graph

sum of degrees

2E=D

directed graphs

a graph where edges have a direction show using arrows.

degree of a vertex

the number of edges incident to a vertex

in and out degrees

in degree is the number of edges toward the vertex

out degree is the number of edges directed out of it

simple graph

a graph in which there are no loops, and there is at most one edge connecting any pair of vertices

subgraph

a graph made from a subset of the vertices and edges of another graph

connected

a graph where there is a path (a walk in which no vertex or edge is repeated) between every pair of vertices

strongly connected

a directed graph where there is a directed path from every vertex to every other vertex

complete graph

a simple graph where every pair of vertices is connected by an edge

formula for number of edges

E = n(n-1)/2

weighted graph

a graph where each edge is assigned a weight such as a distance or cost

weighted adjacency table

summarizes the weights on a graph, - symbol indicates that two vertices are not adjacent

walk

a route through a graph along edges from one vertex to the next (edges and vertices can repeat).

trail

a walk in which no edge is repeated but a repeated vertex is allowed

path

a walk in which no edge or vertex is repeated

circuit

a walk that starts and finishes at the same vertex with no edges repeated (vertices can be repeated)

cycle

a walk that starts and finishes at the same vertex where no edge or vertex is repeated

tree

a connected graph with no cycles

spanning tree

a subgraph that contains all the vertices of the original connected graph, is connected and has no cycles and n-1 edges