Section 1: Fundamentals Flashcards

1
Q

Graph

A

A pair (V, E), where V is any finite set, and E is a set whose elements are pairs of elements from V

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
2
Q

Vertex set

A

The set V in (V, E), sometimes written V(G)

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
3
Q

Edge set

A

The set E in (V, E), sometimes written E(G)

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
4
Q

Adjacent vertices

A

there is an edge between them

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
5
Q

Endpoints of an edge

A

the vertices connected by the edge

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
6
Q

incident

A

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.

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
7
Q

Adjacency matrix

A

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.

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
8
Q

Multigraphs

A

Graphs with loops and/or multiple edges

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
9
Q

Directed graph/ Digraph

A

A graph where all the edges are directed from
one vertex to another.

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
10
Q

Formally, a digraph G is a pair (V, E), where V is any finite set, and E is a set whose elements are …

A

ordered pairs of elements from V.

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
11
Q

Weighted graph

A

each edge is given a weighting indicating the
strength of the interaction the edge represents

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
12
Q

Subgraph

A

a graph H obtained from G by deleting vertices and/or edges

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
13
Q

Induced subgraph

A

a subgraph H of G obtained by deleting only vertices (and the edges incident with the deleted vertices).

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
14
Q

Thus, if U is a subset of the vertices, we can refer to the subgraph induced by U: this is the graph
with …..

A

vertex-set U and edge-set {vw ∈ E : v, w ∈ U}.

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
15
Q

Spanning subgraph

A

a subgraph of G obtained by deleting only edges.

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
16
Q

Walk from u to v

A

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.

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
17
Q

Path from u to v

A

a walk from u to v in which all the vertices
w1, . . . , wp are distinct.

18
Q

Connected graph

A

if, for every two distinct vertices u, v ∈ V, there is a path in G from u to v

19
Q

Disconnected graph

A

Graph that is not connected

20
Q

Connected component

A

We say that a subgraph H of G is a connected component of G if H
is a maximal connected subgraph of G

21
Q

Degree of vertex

A

Number of edges incident with the vertex

22
Q

In a simple graph on n vertices, the degree of a vertex cannot be more than

23
Q

Minimum degree

A

min_(v∈V(G))d(v)

24
Q

Maximum degree

A

max_(v∈V(G))d(v)

25
Isolated vertex
A vertex of degree zero
26
Degree sequence
A list of all of the degrees of the vertices in the graph, often listed in increasing order
27
Isomorphic graphs
if one graph can be obtained from the other by changing the labels
28
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
29
there is an isomorphism from G1 to G2 if and only if ....
there is an isomorphism from G2 to G1.
30
If G1 and G2 are isomorphic, then: * G1 and G2 have the same number of ___ and the same number of ____
vertices and edges,
31
If G1 and G2 are isomorphic, then: G1 and G2 have the same
degree sequence
32
If G1 and G2 are isomorphic, then: G1 is connected if and only if ...
G2 is connected
33
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.
34
Clique
Complete graph
35
How many edges does K_n have?
(n ) (2 ) = 1/2n(n − 1) edges.
36
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}
37
Endpoints of path
The vertices corresponding to v1 and vn in Pn
38
How many edges does a path have?
n − 1
39
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}.
40
Notice that Cn can be obtained from Pn by adding
one extra edge between the endpoints of the path
41
How many edges does a cycle have?
n