Section 1: Fundamentals Flashcards
Graph
A pair (V, E), where V is any finite set, and E is a set whose elements are pairs of elements from V
Vertex set
The set V in (V, E), sometimes written V(G)
Edge set
The set E in (V, E), sometimes written E(G)
Adjacent vertices
there is an edge between them
Endpoints of an edge
the vertices connected by the edge
incident
If e = uv is an edge of G, we say that u and v are
incident with e, and if two edges e and f have a common endpoint we
say that e and f are incident.
Adjacency matrix
an n × n matrix in which , the entry in the column labelled u and the row labelled v is 1 if and only if uv is an edge.
Multigraphs
Graphs with loops and/or multiple edges
Directed graph/ Digraph
A graph where all the edges are directed from
one vertex to another.
Formally, a digraph G is a pair (V, E), where V is any finite set, and E is a set whose elements are …
ordered pairs of elements from V.
Weighted graph
each edge is given a weighting indicating the
strength of the interaction the edge represents
Subgraph
a graph H obtained from G by deleting vertices and/or edges
Induced subgraph
a subgraph H of G obtained by deleting only vertices (and the edges incident with the deleted vertices).
Thus, if U is a subset of the vertices, we can refer to the subgraph induced by U: this is the graph
with …..
vertex-set U and edge-set {vw ∈ E : v, w ∈ U}.
Spanning subgraph
a subgraph of G obtained by deleting only edges.
Walk from u to v
a sequence of vertices w1, . . . , wp (for some natural number p ≥ 2), with w1 = u and wp = v, such that wiwi+1 is an edge for every 1 ≤ i ≤ p − 1.
Path from u to v
a walk from u to v in which all the vertices
w1, . . . , wp are distinct.
Connected graph
if, for every two distinct vertices u, v ∈ V, there is a path in G from u to v
Disconnected graph
Graph that is not connected
Connected component
We say that a subgraph H of G is a connected component of G if H
is a maximal connected subgraph of G
Degree of vertex
Number of edges incident with the vertex
In a simple graph on n vertices, the degree of a vertex cannot be more than
n − 1
Minimum degree
min_(v∈V(G))d(v)
Maximum degree
max_(v∈V(G))d(v)
Isolated vertex
A vertex of degree zero
Degree sequence
A list of all of the degrees of the vertices in the graph, often listed in increasing order
Isomorphic graphs
if one graph can be obtained from the other by changing the labels
Isomorphism from G1 = (V1, E1) to G2 = (V2, E2)
a bijection f : V1 → V2 such that, for every u, v ∈ V1, f(u)f(v) ∈ E2 if and only if uv ∈ E1
there is an isomorphism from G1 to G2 if and only if ….
there is an isomorphism from G2 to G1.
If G1 and G2 are isomorphic, then:
* G1 and G2 have the same number of ___ and the same number of ____
vertices and edges,
If G1 and G2 are isomorphic, then:
G1 and G2 have the same
degree sequence
If G1 and G2 are isomorphic, then:
G1 is connected if and only if …
G2 is connected
Complete graph
a complete graph on n vertices, denoted Kn, is a graph on n vertices in which every pair of distinct vertices forms an edge.
Clique
Complete graph
How many edges does K_n have?
(n )
(2 ) = 1/2n(n − 1) edges.
Path on n vertices, denoted P_n
a graph that is isomorphic to the graph (V, E) where V = {v1, . . . , vn} and E = {vivi+1: 1 ≤
i ≤ n − 1}
Endpoints of path
The vertices corresponding to v1 and vn in Pn
How many edges does a path have?
n − 1
Cycle on n vertices, denoted C_n
s a graph that is isomorphic to the graph (V, E) where V = {v1, . . . , vn} and E = {vivi+1 : 1 ≤ i ≤ n − 1} ∪ {vnv1}.
Notice that Cn can be obtained from Pn by adding
one extra edge
between the endpoints of the path
How many edges does a cycle have?
n
