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 one-to-one 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[n-1], e[n], v[n] of vertices v[i] and edges e[i] such that edge e[i] joins vertex v[i-1] 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 |