A graph G consists of point (vertices or nodes) which are connected by lines (arcs or edges)
1 of 16
subgraph
A subgraph of G is a graph, each of whose vertices belongs to G and each of whose edges also belongs to G
2 of 16
Weighted Graph
If a graph has a number associated with each edge (usually called its weight) then the graph is called as weighted graph or network
3 of 16
degree/valency
The degree or vlaency of a vertex is the number of edges incident to it. A vertex is odd (even) if it has odd (even) degeree.
4 of 16
path
a path is a finite sequence of edges, such that the end vertex of one edge inthe sequence is the start vertex of the next, and in which no vertex appears more than once
5 of 16
walk
a walk is a path where you may visit vertices more than once
6 of 16
cycle (circuit)
A cycle or circuit is a closed path ie the end vertex of the last edge is the start vertex of the first edge
7 of 16
connected
2 vertices are connected if there is a path between them. A graph is connected if all its vertices are connected
8 of 16
digraph
If tthe edges of a graph have a direciton associated with them they are known as directed edges and the graph is known as a digraph.
9 of 16
tree
a tree is a connected graph with no cycles
10 of 16
spanning tree
a spanning tree of a graph g is a subgraph which includes all the vertices of g and is also a tree
11 of 16
minimum spanning tree
a mst is a spanning tree such that the total length of its arcs is as small as possible
12 of 16
complete graph
a graph in which each of the n vertices is connected to every other vertex is called a complete graph
13 of 16
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 with in a set
14 of 16
matching
a matching is the pairing of some or all of the elements of one set, x, with elements of a secod set, y. if every member of x is paired with a member of y the matching is said to be complete
15 of 16
alternating path
an alternating path starts at an unconnected vertex in one set and ends at an unconnected vertex in the other set. Edges alternate between those not in and in the initial matching
16 of 16
Other cards in this set
Card 2
Front
A subgraph of G is a graph, each of whose vertices belongs to G and each of whose edges also belongs to G
Back
subgraph
Card 3
Front
If a graph has a number associated with each edge (usually called its weight) then the graph is called as weighted graph or network
Back
Card 4
Front
The degree or vlaency of a vertex is the number of edges incident to it. A vertex is odd (even) if it has odd (even) degeree.
Back
Card 5
Front
a path is a finite sequence of edges, such that the end vertex of one edge inthe sequence is the start vertex of the next, and in which no vertex appears more than once
Comments
No comments have yet been made