Chapter 5: Mathematics of Graphs Flashcards
1
Q
Trees in electric Circuits made by
A
Gustav Krichoff
2
Q
Enumeration of Chemical Isomers by
A
- Arthur Cayley
- James J. Sylvester
- George Polya
3
Q
Four Colors of Maps by
A
- Francis Guthrie
- Auguste De Morgan
4
Q
Most common Known Applications of Graph Theory
A
- Transportation networks
- Internet
- Genetic interaction network
- Ecological networks
5
Q
- Are points in a graph
- Non-empty set of elements
A
Vertices
6
Q
- Are lines in a graph
- Family of two element subsets of V(G)
A
Edges
7
Q
- set V(G)
A
Vertex set
8
Q
- set E(G)
A
Edge set
9
Q
- If e = uv is an edge in G, u and v are ______
A
adjacent vertices
10
Q
- Adjacent vertices in an edge G are ____ with each other
A
incident
11
Q
- Number of edges connected with a vertex as an end-vertex
A
Degree of a vertex
12
Q
- Graphs without multiple edges or self-loops
A
Simple graph
13
Q
- When 2 vertices must be written twice because there are two edges connecting 1 and 2
A
Multiple edges
14
Q
- Edge joining it and itself
A
Loop
15
Q
- multiple edges but no loops
A
Multigraph
16
Q
- loops and multiple edges
A
Pseuodograph
17
Q
- if every pair of points can be joined by an edge
A
Connected graph
18
Q
- if an edge does not join every pair of points
A
Disconnected graph
19
Q
Eulerian is if and only if
A
- degree of each vertex of G is even.
- graph is a Euler circuit
19
Q
- path using every edge of the graph G exactly once
A
Euler path
20
Q
- if and only if the degree of each vertex of G is even.
A
Eulerian
21
Q
- Euler path that returns to its start
A
Euler circuit
22
Q
invented Icosian game
A
Sir William Rowan Hamilton
23
Q
What year did the Icosian game get invented
A
1857
24
Q
- puzzle-game involved hunting for Hamiltonian cycle
- distributed as a dodecahedron graph with a hole at each vertex.
A
Icosian game
25
Q
- polyhedron with twelve flat faces
A
Dodecahedron
26
Q
- graph G is a path which visits every vertex in G exactly once
A
Hamilton path
27
Q
Hamiltonian is if and only if
A
- the graph has a Hamilton circuit.
28
Q
- Hamilton path that returns to its start.
A
Hamiltonian circuit
29
Q
- Graph in which edge is associated with a value
A
Weighted graph
30
Q
- Value in a weighted graph
A
Weight
31
Q
- from vertex u to vertex v is a sequence of adjacent edges starting u and ending in v such that the end of each edge other than the last one is the start of the next edge in the sequence.
A
Path
32
Q
- sum of the weights of the edges of the path.
A
Length of a path
33
Q
- Dutch computer scientist from Netherlands
- Developed an algorithm that finds the shortest path between vertices in a connected weighted graph
A
Edsger Wybe Dijkstra (May 11, 1930 – August 6, 2002)
34
Q
- an assignment of colors to its vertices so that no two adjacent vertices have the same color
A
Coloring of a graph
35
Q
A
