A graph which has numbers associated with each edge
2 of 26
Subgraph
Part of the original graph, G, whose nodes and arcs belong to G
3 of 26
Valency
The number of arcs incident to the node
4 of 26
Path
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
5 of 26
Cycle
A closed 'path', i.e. the end vertex of the last edge is the start vertex of the first edge
6 of 26
Walk
A path which you are allowed to return to vertices more than once
7 of 26
Connected graph
Two vertices are connected if there is an arc between them. A graph is connected if all its vertices are connected
8 of 26
Loop
An edge that starts and finishes at the same vertex
9 of 26
Simple graph
One in which there are no loops and they don't have more than one edge connecting any pair of vertices
10 of 26
Digraph
If the edges of a graph have a direction associated with them they are known as directed edges and the graph is a digraph
11 of 26
Tree
A connected graph with no cycles
12 of 26
Spanning tree
A subgraph which includes all the vertices of the original graph and is also a tree
13 of 26
Bipartite graph
Consists of two sets of vertices, X and Y. The edges only join vertices in X with vertices in Y, not vertices within a set
14 of 26
Complete graph
A graph in which every vertex is directly connected by an edge to each of the other vertices. If the graph has n vertices, then the connected graph is denoted by Kn
15 of 26
Complete bipartite graph
A bipartite graph such that every pair of vertices in the two sets are adjacent
16 of 26
Isormorphic graphs
Graphs that show the same information but are drawn differently
17 of 26
Adjacency matrix
A matrix which records the number of direct links between vertices
18 of 26
Distance matrix
A matrix which records the weights on the edges of a weighted graph
19 of 26
Algorithm
A precise set of instructions so clear that anyone can use them to achieve a particular goal in a specified number of steps
20 of 26
Traversible (Eulerian) graph
A graph in which every vertex is even, making it possible to traverse every arc once and return to the start vertex
21 of 26
Semi-traversible (Semi-Eulerian) graph
A graph with precisely two odd vertices, making it possible to traverse every arc once, provided you start and finish at the odd vertices
22 of 26
A non-traversible graph
A graph with more than two odd vertices
23 of 26
Matching
A one to one pairing of some or all of the nodes of one set in a bipartite graph with nodes of the alternate set. One to one means each node from one set is matched with only one node from the alternate set
24 of 26
Maximal matching
A matching in which the number of arcs is as big as possible
25 of 26
Complete matching
A matching in of two sets, each containing n nodes, which has n arcs
26 of 26
Other cards in this set
Card 2
Front
A graph which has numbers associated with each edge
Back
Weighted graph/network
Card 3
Front
Part of the original graph, G, whose nodes and arcs belong to G
Back
Card 4
Front
The number of arcs incident to the node
Back
Card 5
Front
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
Comments
No comments have yet been made