Points ( vertices or nodes ) which are connected by lines ( edges or arcs ).
1 of 23
Subgraph
A graph, G, each of whose nodes belongs to G and each of whose arcs belongs to G.
2 of 23
Network
A graph with a number associated with each arc (usually called its weight).
3 of 23
Valency (degree/order)
The number of arcs incident to the nodes. A node is odd ( even ) if it has odd ( even ) degree.
4 of 23
Path
A finite sequence of arcs, such that the end node of one arc in the sequence is the start node of the next, and in which no node appears more then once.
5 of 23
Cycle
A closed path, ie the end node of the last arc is the start node of the first arc.
6 of 23
Loop
An arc that starts and finishes at the same node.
7 of 23
Incidence Matrix
Matrix of connections that can be drawn up to illistrate a graph. Non digraph matrices will be symmetrical.
8 of 23
Eulerian Cycle
A cycle in which every node of the graph is visited only once. A ........ graph cannot have any odd arcs.
9 of 23
Semi-Eulerian graph
Has exactly two odd vertices
10 of 23
Simple graph
A graph with no loops and no more than one arc connecting any pair of nodes.
11 of 23
Connected graph
All its nodes have paths between them (are connected).
12 of 23
Plannar graph
The graph can be drawn without crossing any arcs
13 of 23
Complete graph
Every vertex is connected to every other vertex
14 of 23
Tree
A connected graph with no cycles.
15 of 23
Spanning tree
A subgraph of a graph, G, which includes all the nodes of G and is also a tree.
16 of 23
Digraph
The arcs of a graph have a direction associated with them.
17 of 23
Bipartite graph
Two sets of nodes X and Y. The arcs only join nodes in X to nodes in Y, not nodes within a set.
18 of 23
Minimum spanning tree (minimum connector)
A spanning tree such that the total length of its arcs is as small as possible.
19 of 23
Matching
A pairing of some or all of the elements of one set, X, with elements of a second set, Y.
20 of 23
Complete matching
Every member of X is paired with a member of Y of the matching.
21 of 23
Isomorphic
Graphs that show the same information but drawn differently.
22 of 23
Eulerian Cycle
A cycle in which every node of the graph is visited only once. A ........ graph cannot have any odd arcs.
23 of 23
Other cards in this set
Card 2
Front
A graph, G, each of whose nodes belongs to G and each of whose arcs belongs to G.
Back
Subgraph
Card 3
Front
A graph with a number associated with each arc (usually called its weight).
Back
Card 4
Front
The number of arcs incident to the nodes. A node is odd ( even ) if it has odd ( even ) degree.
Back
Card 5
Front
A finite sequence of arcs, such that the end node of one arc in the sequence is the start node of the next, and in which no node appears more then once.
Comments
No comments have yet been made