Use LEFT and RIGHT arrow keys to navigate between flashcards;
Use UP and DOWN arrow keys to flip the card;
H to show hint;
A reads text to speech;
13 Cards in this Set
 Front
 Back
Undirected graph 
An undirected graph G is a finite set of vertices V[G] and a finite set of edges E[G], along with a function i: E[G] > V[G] x V[G]. For any edge e€E[G], if i(e) = (a,b), we say that vertices a and b are joined by edge e. 

Directed graph 
A directed graph G is a finite set of vertices V[G] and a finite set of edges E[G], along with a function i: E[G] > V[G] x V[G]. For any edge e€E[G], if i(e) = (a, b), we say that edge e joins vertex a to vertex b. 

Isomorphic graphs 
Let G be a graph with vertex set V[G] and edge set E[G], and let H be a graph with vertex set V[H] and edge set E[H]. Then G is isomorphic to H if there are onetoone correspondences (alpha): V[G] > V[H] and (beta): E[G] > E[H] such that, for any edge e€E[G], e joins vertex v to vertex w iff beta(e) joins vertex alpha(v) to vertex alpha(w). 

Path 
Let G be a graph. A path in G is a sequence v[0], e[1], v[1], e[2], v[2],..., v[n1], e[n], v[n] of vertices v[i] and edges e[i] such that edge e[i] joins vertex v[i1] to vertex v[i], where n>=1. 

Circuit 
A circuit is a path with v[0]=v[n] 

Simple 
A path or circuit is simple if the edges in the sequence are all distinct 

Connected 
A graph is connected is there is a path connecting any two pairs of vertices 

Tree 
A tree is a graph T with a specified vertex r, called the root, with the property that, for any vertex v in T where v!=r, there is a unique simple path from r to v. 

Degree 
Let G be an undirected graph, and let x€V[G] be a vertex. Let D[1] be the set of all edges e€E[G] such that such that i(e)=(x,b) for some b, and let D[2] be the set of all edges e€E[G] such that i(e)=(a,x) for some a. Then the degree of x is D[1] + D[2]. 

Outdegree 
Let G be a directed graph, and let x€V[G] be a vertex. Let D be the set of all edges e€E[G] such that i(e)=(x,b) for some b. Then the outdegree of x is D. 

Indegree 
Let G be a directed graph, and let x€V[G] be a vertex. Let D be the set of all edges e€E[G] such that i(e)=(a,x) for some a. Then the indegree of x is D. 

Euler path 
A simple path using all the edges of the graph. 

Euler circuit 
A simple circuit using all the edges of the graph 