Reading...
Play button
Play button
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;
25 Cards in this Set
- Front
- Back
|
Graph
|
A graph G consists of points (vertices or nodes) which are connected by lines (edges or arcs)
|
|
|
Subgraph
|
A subgraph of G is a graph, each of whose vertices belongs to G and each of whose edges belongs to G.
|
|
|
Weighted graph/network
|
If a graph has a number associated with each edge (usually called its weight) then the graph is called a weighted graph of network.
|
|
|
Degree/valency
|
The degree or valency of a vertex is the number of edges incident to it. A vertex is odd (even) if it has odd (even) degree.
|
|
|
Path
|
A path is a finite sequence of edges, such that the end vertex of one edge in the sequence is the start vertex of the next, and in which no vertex appears more than once.
|
|
|
Cycle
|
A cycle (circuit) is a closed path, ie. the end vertex of the last edge is the start vertex of the first edge.
|
|
|
Connected vertices
|
Two vertices are connected if there is a path between them. A graph is connected if all its vertices are connected.
|
|
|
Digraph
|
If the edges of a graph have a direction associated with them they are known as directed edges and the graph is known as a digraph.
|
|
|
Tree
|
A tree is a connected graph with no cycles.
|
|
|
Spanning Tree
|
A spanning tree of a graph G is a subgraph which includes all the vertices of G and is also a tree.
|
|
|
Graph
|
A graph G consists of points (vertices or nodes) which are connected by lines (edges or arcs)
|
|
|
Subgraph
|
A subgraph of G is a graph, each of whose vertices belongs to G and each of whose edges belongs to G.
|
|
|
Weighted graph/network
|
If a graph has a number associated with each edge (usually called its weight) then the graph is called a weighted graph of network.
|
|
|
Degree/valency
|
The degree or valency of a vertex is the number of edges incident to it. A vertex is odd (even) if it has odd (even) degree.
|
|
|
Path
|
A path is a finite sequence of edges, such that the end vertex of one edge in the sequence is the start vertex of the next, and in which no vertex appears more than once.
|
|
|
Cycle
|
A cycle (circuit) is a closed path, ie. the end vertex of the last edge is the start vertex of the first edge.
|
|
|
Connected vertices
|
Two vertices are connected if there is a path between them. A graph is connected if all its vertices are connected.
|
|
|
Digraph
|
If the edges of a graph have a direction associated with them they are known as directed edges and the graph is known as a digraph.
|
|
|
Tree
|
A tree is a connected graph with no cycles.
|
|
|
Spanning Tree
|
A spanning tree of a graph G is a subgraph which includes all the vertices of G and is also a tree.
|
|
|
Mimimum spanning tree
|
A mimimum spanning tree (MST) is a spanning tree such that the total length of its arcs is as small as possible. (MST is sometimes called a minimum connector.)
|
|
|
Complete graph
|
A graph in which each of the n vertices is connected to every other vertex is called a complete graph
|
|
|
Total Float
|
The total float F(i,j) of activity (i,j) is defined to be F(i,j)=l(J)-e(i)-duration
where: e(i) is the earliest time for even i and l(J) is the latest time for event J |
|
|
Bipartite graph
|
A bipartite graph consists of two sets of vertices X and Y. The edges only join vertices in X to vertices in Y, not vertices within a set.
|
|
|
Matching
|
A matching is the pairing of some or all of the elements of one set, X, with elements of a second set, Y. If every member of X is paired with a number of Y the matching is said to be a complete matching.
|
