1
Q
What is a graph?
A
A representation of a set of points (vertices) and how they are connected by lines (edges).
2
Q
What are the points in a graph called?
A
Vertices.
3
Q
What does the degree of a vertex represent?
A
The number of edges connected to that vertex.
4
Q
What are multiple edges in a graph?
A
Edges that connect the same pair of vertices.
5
Q
What is a loop in a graph?
A
An edge that connects a vertex to itself.
6
Q
What is a simple graph?
A
A graph that contains no loops or multiple edges.
7
Q
What is a directed graph (digraph)?
A
A graph where edges have a direction, indicated by arrows.
8
Q
What is a walk in graph theory?
A
A sequence of edges that connects a sequence of vertices.
9
Q
What is a path in graph theory?
A
A walk in which no vertex appears more than once.
10
Q
What is a cycle in graph theory?
A
A walk that starts and ends at the same vertex.
11
Q
What are Eulerian graphs?
A
Graphs that contain a walk that includes every edge exactly once.
12
Q
What are Hamiltonian graphs?
A
Graphs that contain a walk that includes every vertex exactly once.
13
Q
What is a connected graph?
A
A graph where there is a path between any two vertices.
14
Q
What is a disconnected graph?
A
A graph that consists of two or more components that are not connected.
15
Q
What is a tree in graph theory?
A
A connected graph that contains no cycles.
16
Q
What is a planar graph?
A
A graph that can be drawn on a plane without any edges crossing.
17
Q
What is the four-colour theorem?
A
A theorem stating that any planar graph can be coloured with four colours such that no two adjacent vertices share the same colour.
18
Q
What does it mean for two graphs to be isomorphic?
A
Two graphs G1 and G2 are isomorphic if there is a one-to-one correspondence between their vertices such that the number of edges between corresponding vertices is the same.
19
Q
What does the term ‘degree of a vertex’ refer to?
A
The degree of a vertex is the number of edges incident to that vertex.
20
Q
What is the maximum number of edges in a simple graph with n vertices?
A
The maximum number of edges in a simple graph with n vertices is given by n(n-1)/2.
21
Q
What are the components of a graph?
A
Components are maximal connected subgraphs within a disconnected graph.
22
Q
What is the relationship between labelled and unlabelled graphs?
A
Labelled graphs have specific names for vertices, while unlabelled graphs do not; counting them reveals differences in structure.
23
Q
What does it mean for two vertices in a graph to be adjacent?
A
Two vertices v and w are adjacent if there is an edge vw joining them.
24
Q
What is the contribution of a loop to the degree of a vertex?
A
A loop at vertex v contributes 2 to the degree of v.
25
What is an isolated vertex?
A vertex of degree 0 is called an isolated vertex.
26
What is an end-vertex?
A vertex of degree 1 is known as an end-vertex.
27
What is the handshaking lemma?
The handshaking lemma states that the sum of all vertex-degrees in a graph is even, as it equals twice the number of edges.
28
What does the handshaking lemma imply about vertices of odd degree?
It implies that the number of vertices of odd degree in any graph is even.
29
How can subgraphs be obtained from a graph?
Subgraphs can be obtained by deleting edges and vertices from the original graph.
30
What does G - e represent?
G - e denotes the graph obtained from G by deleting the edge e.
31
What does G - v represent?
G - v denotes the graph obtained from G by deleting the vertex v and its incident edges.
32
What is the adjacency matrix of a graph?
The adjacency matrix A is an n x n matrix where the entry A[i][j] represents the number of edges joining vertices i and j.
33
What is the incidence matrix of a graph?
The incidence matrix M is an n x m matrix where M[i][j] is 1 if vertex i is incident to edge j, and 0 otherwise.
34
What is a complete graph?
A complete graph is a simple graph where each pair of distinct vertices is adjacent, denoted by Kn.
35
What is a cycle graph?
A cycle graph is a connected graph that is regular of degree 2, denoted by Cn.
36
What is a path graph?
A path graph is obtained from a cycle graph by removing an edge, denoted by Pn.
37
What is a wheel graph?
A wheel graph is obtained by joining each vertex of a cycle graph to a new vertex, denoted by Wn.
38
What is a regular graph?
A regular graph is one where each vertex has the same degree.
39
What is a cubic graph?
A cubic graph is a regular graph where each vertex has degree 3.
40
What is an example of a cubic graph?
The Petersen graph.
41
What is the null graph Nn?
The null graph Nn is a regular graph of degree 0.
42
What are Platonic graphs?
Platonic graphs are formed from the vertices and edges of the five regular solids: tetrahedron, octahedron, cube, icosahedron, and dodecahedron.
43
What defines a bipartite graph?
A bipartite graph can have its vertex set split into two disjoint sets A and B, where each edge joins a vertex from A to a vertex from B.
44
How can you color the vertices of a bipartite graph?
The vertices can be colored black and white such that each edge connects a black vertex in A and a white vertex in B.
45
What is a complete bipartite graph?
A complete bipartite graph is one where each vertex in set A is connected to every vertex in set B by exactly one edge.
46
How is a bipartite graph denoted?
A bipartite graph with r black vertices and s white vertices is denoted by Kr,s.
47
What is the k-cube Qk?
The k-cube Qk is a graph whose vertices correspond to binary sequences of length k, with edges connecting sequences that differ in one position.
48
What are the properties of the k-cube Qk?
Qk has 2^k vertices and k * 2^(k-1) edges, and is regular of degree k.
49
What is the complement of a simple graph G?
The complement G of a simple graph G has the same vertex set, where two vertices are adjacent if and only if they are not adjacent in G.
50
What is the complement of a complete graph?
The complement of a complete graph is a null graph.
51
What is the complement of a complete bipartite graph?
The complement of a complete bipartite graph is the union of two complete graphs.
52
What is a self-complementary graph?
A self-complementary graph is isomorphic to its complement.
53
What is the line graph L(G) of a simple graph G?
The line graph L(G) has vertices corresponding to the edges of G, with edges connecting vertices if the corresponding edges of G are adjacent.
54
# NOT NEEDED
What is an automorphism of a simple graph G?
An automorphism is a one-to-one mapping of the vertex set of G onto itself that preserves adjacency.
55
# NOT NEEDED
What is the automorphism group T(G) of a graph G?
The automorphism group T(G) consists of all automorphisms of G under composition.
56
What is a complete tripartite graph?
A complete tripartite graph Kr,s,t consists of three sets of vertices of sizes r, s, and t, with edges joining vertices from different sets.
57
How many edges does a bipartite graph Kr,s have?
Kr,s has r * s edges.
58
What is the relationship between the number of vertices and edges in a complete bipartite graph?
A complete bipartite graph Kr,s has r + s vertices and r * s edges.
59
What is a walk in a graph?
A finite sequence of edges connecting vertices, where any two consecutive edges are adjacent or identical.
60
What distinguishes a trail from a walk?
A trail is a walk in which all edges are distinct.
61
What is a cycle in a graph?
A closed path where the initial and final vertices are the same.
62
What is the significance of cycles in bipartite graphs?
In a bipartite graph, every cycle has even length.
63
What is a disconnecting set in a connected graph?
A set of edges whose removal disconnects the graph.
64
What is a cutset?
A disconnecting set in a graph, no proper subset of which is a disconnecting set.
65
What is a bridge in graph theory?
A cutset consisting of a single edge whose removal increases the number of components in the graph.
66
What does edge connectivity X(G) represent?
The size of the smallest cutset in a connected graph G, indicating the minimum number of edges needed to disconnect G.
67
What is the relationship between the number of edges and components in a simple connected graph?
A simple connected graph with n vertices has at least n-1 edges and at most n(n-1)/2 edges.
68
What is the condition for a graph to be k-edge connected?
The edge connectivity X(G) must be greater than or equal to k.
69
What does it mean for a graph to be connected?
A graph is connected if there is a path between every pair of vertices.
70
What is the length of a walk?
The number of edges in the walk.
71
What is a closed trail?
A trail where the initial and final vertices are the same.
72
What is the definition of a regular graph?
A graph where each vertex has the same degree.
73
What is the maximum number of edges in a complete graph with n vertices?
n(n-1)/2.
74
What is the minimum number of edges required to ensure connectivity in a graph with n vertices?
At least n-1 edges.
75
What is a cutset in a graph?
A cutset is a set of edges whose removal disconnects the graph.
76
What does it mean for a graph to be k-edge connected?
A graph is k-edge connected if the minimum number of edges that need to be removed to disconnect the graph is greater than k.
77
What is a separating set in a connected graph?
A separating set is a set of vertices whose deletion disconnects the graph.
78
What is a cut-vertex?
A cut-vertex is a vertex whose removal increases the number of connected components in the graph.
79
How is the connectivity K(G) of a graph defined?
K(G) is the size of the smallest separating set in the graph G.
80
What is the girth of a graph?
The girth is the length of the shortest cycle in the graph.
81
What is an Eulerian graph?
A connected graph is Eulerian if there exists a closed trail that contains every edge exactly once.
82
What is a semi-Eulerian graph?
A semi-Eulerian graph has a trail that contains every edge but may not return to the starting vertex.
83
What is the necessary and sufficient condition for a graph to be Eulerian?
A connected graph is Eulerian if and only if the degree of each vertex is even.
84
How can the number of walks of length 2 from vertex vi to vj be represented?
It can be represented as the (i,j)-th entry of the adjacency matrix squared, A².
85
What is the significance of the sum of the diagonal entries of A²?
It equals twice the number of edges in the graph.
86
What does it mean for a graph to be disconnected?
A graph is disconnected if there exists at least one pair of vertices that cannot be connected by a path.
87
What is a trail in graph theory?
A trail is a walk in which no edge is repeated.
88
What must the starting and ending vertices be in a semi-Eulerian trail?
The initial vertex must be one of the odd degree vertices, and the final vertex must be the other.
89
What does the handshaking lemma state about odd degree vertices in a graph?
A graph cannot have exactly one vertex of odd degree.
90
What is Fleury's algorithm used for?
It is an algorithm for constructing an Eulerian trail in a given Eulerian graph.
91
What is the first step in Fleury's algorithm?
Start at any vertex and traverse the edges in an arbitrary manner, erasing edges as they are traversed.
92
What is a bridge in the context of Fleury's algorithm?
A bridge is an edge whose removal increases the number of connected components in the graph.
93
What must be avoided when traversing edges in Fleury's algorithm?
Use a bridge only if there is no alternative.
94
What is a Hamiltonian graph?
A graph that contains a closed trail passing exactly once through each vertex.
95
What is a semi-Hamiltonian graph?
A graph that has a path passing through every vertex but does not form a Hamiltonian cycle.
96
What is Dirac's theorem regarding Hamiltonian graphs?
If a simple graph has n vertices and each vertex has a degree of at least n/2, then the graph is Hamiltonian.
97
What is Ore's theorem regarding Hamiltonian graphs?
If a simple graph has n vertices and the sum of the degrees of any two non-adjacent vertices is greater than n, then the graph is Hamiltonian.
98
What is the relationship between Eulerian and Hamiltonian graphs?
Eulerian graphs focus on edge traversal, while Hamiltonian graphs focus on vertex traversal.
99
What is the minimum number of trails needed to cover all edges in a graph with k vertices of odd degree?
The minimum number of trails is k/2.
100
What is the significance of the wheel graph Wn?
A graph that consists of a cycle with an additional central vertex connected to all vertices of the cycle.
101
# NOT NEEDED
What does it mean for a graph to be randomly traceable?
A graph is randomly traceable from a vertex if starting from that vertex and traversing edges arbitrarily eventually leads to an Eulerian trail.
102
What is the relationship between a graph and its line graph regarding Eulerian properties?
The line graph of a simple Eulerian graph is also Eulerian.
103
Can a non-Eulerian graph have an Eulerian line graph?
Yes, if the line graph of a simple graph G is Eulerian, it does not necessarily mean G is Eulerian.
104
What is the condition for a knight to visit all squares of an n x n chessboard exactly once and return to its starting point?
If n is odd, it is not possible for a knight to achieve this.
105
What does Dirac's theorem state regarding the degree of a vertex in a graph?
It states that if deg(v) > n/2, then the graph is Hamiltonian; however, this cannot be replaced by deg(v) > (n - 1)/2.
106
What is the Petersen graph known for?
It is a classic example of a non-Hamiltonian graph.
107
What is the shortest path problem in graph theory?
It involves finding the minimum total weight path between two vertices in a weighted graph.
108
What is a weighted graph?
A graph where each edge has a numerical weight representing distance, cost, or time.
109
What does it mean for a graph to be Eulerian?
A graph is Eulerian if it contains an Eulerian circuit, meaning all edges can be traversed exactly once in a closed loop.
110
What is a semi-Eulerian trail?
A trail that visits every edge of a graph exactly once but does not return to the starting point.
111
What is the relationship between trees and forests?
A forest is a graph that contains no cycles, and a connected forest is a tree.
112
What are the properties of a tree with n vertices?
A tree with n vertices has n-1 edges, is connected, and contains no cycles.
113
What does it mean for an edge to be a bridge in a tree?
A bridge is an edge that, if removed, would disconnect the tree.
114
What is a spanning tree?
A subgraph that connects all the vertices of a graph without any cycles.
115
What is the cycle rank of a graph?
The number of edges in a spanning forest, defined as y(G) = m - n + k, where m is the number of edges, n is the number of vertices, and k is the number of components.
116
What is a cutset in graph theory?
A set of edges whose removal disconnects the graph.
117
What happens if you add an edge to a tree?
Adding an edge creates exactly one cycle in the tree.
118
What is the handshaking lemma in relation to trees?
The sum of the degrees of the vertices in a tree is equal to twice the number of edges.
119
What is the difference between a spanning tree and a spanning forest?
A spanning tree connects all vertices of a single connected graph, while a spanning forest connects all vertices of a graph with multiple components.
120
What is the corollary related to forests with n vertices and k components?
If G is a forest with n vertices and k components, then G has n - k edges.
121
What is the significance of Cayley's theorem in graph theory?
Cayley's theorem states that there are n^(n-2) distinct labelled trees on n vertices.
122
What can be said about an edge of a connected graph G that appears in every spanning tree?
It is a bridge or cut-edge of the graph.
123
What can be said about an edge of a connected graph G that appears in no spanning tree?
It is not a bridge and does not connect any two components of the graph.
124
What is the relationship between the cutset rank and the number of edges in a subgraph?
The cutset rank must be less than the number of edges in the subgraph.
125
What does it mean for two trees to be isomorphic?
They can be transformed into each other by renaming their vertices.
126
What is the significance of the sequence (a1, a2, ..., an-2) in the context of labelled trees?
It establishes a one-to-one correspondence between labelled trees and sequences of integers that reflect the tree's structure.
127
What is the maximum number of labelled trees on four vertices?
There are 16 non-isomorphic labelled trees on four vertices.
128
What is a linkage in the context of labelled trees?
A pair of labelled trees (A, B) where B is obtained from A by adding an edge to increase the degree of a vertex.
129
What is the relationship between the dimensions of the cycle subspace W and the cutset subspace W*?
The dimensions are equal to the number of vertices and the cutset rank of the graph, respectively.
130
How is a labelled tree A with degree k - 1 obtained from a labelled tree B?
By removing one edge incident with a vertex v and joining it to any vertex of another subtree.
131
What is the total number of labelled trees on n vertices?
n^(n-2)
132
What does the matrix-tree theorem state about a connected simple graph G?
The number of spanning trees of G is equal to the cofactor of any element of its degree matrix.
133
What is the number of spanning trees of the complete graph K_n?
n^(n-2)
134
What is the minimum connector problem in graph theory?
Finding a spanning tree that connects n cities with the least total edge weight.
135
What algorithm is used to solve the minimum connector problem?
A greedy algorithm that chooses edges of minimum weight without forming cycles.
136
What does the notation T(n, k) represent?
The number of labelled trees on n vertices with k edges.
137
What is the significance of the cofactor in the matrix-tree theorem?
It represents the number of spanning trees in the graph represented by the matrix.
138
What is the formula for the number of labelled trees on n vertices derived from T(n, k)?
T(n, k) = (n - 1)T(n - 1, k - 1)
139
What is the outcome of applying the greedy algorithm to a weighted graph with cities?
It results in a spanning tree that connects all cities with minimal total edge weight.
140
What do carbon and hydrogen atoms represent in a molecular graph?
Carbon atoms appear as vertices of degree 4, and hydrogen atoms appear as vertices of degree 1.
141
What is the general formula for alkanes?
C_nH_{2n+2}.
142
What is a breadth-first search?
A search method that visits all adjacent vertices before moving deeper into the tree.
143
What is a depth-first search?
A search method that penetrates as deeply as possible into a tree before backtracking.
144
What is a minimum-weight spanning tree?
A spanning tree that has the smallest possible total edge weight.
145
What is the significance of K3,3 and K5 in graph theory?
They are examples of non-planar graphs.
ice
flashcards
Decks in class (8)
# Cards
