ECM 1415 Graph Theory Flashcards

You may prefer our related Brainscape-certified flashcards:
1
Q

Simple Graph

A

Each edge connects two different vertices and no two edges connect the same pair of vertices.

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

Multigraphs

A

Have multiple edges connecting the same two vertices.

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

Pseudograph

A

May include loops, as well as multiple edges connecting the same pair of vertices

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

Directed graph

A

Each edge is associated with an ordered pair of vertices (u, v)
Such an edge is said to start at u and end at v
u is the initial vertex of this edge and is adjacent to v and v is the terminal (end) vertex of this edge and is adjacent from u

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

Simple Directed Graph

A

No loops or multiple edges

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

Directed multigraph

A

Multiple directed edges

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

Mixed Graph

A

Can have directed and undirected, with multiple edges and loops

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

Neighborhood

A

The set of all neighbours of a vertex

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

Degree

A

The number of incident edges a vertex has
- A loop at a vertex contributes 2 to the degree of that vertex

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

Handshaking Theorem

If G = (V, E) is an undirected graph with m edges then,

A

2m = Total number of degrees of freedom

Each edge contributes 2 to the degree count of all vertices because an edge is incident with exactly 2 (possibly equal) vertices

This means that the sum of the degrees of the vertices is twice the number of edges

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

In-degrees and Out-degrees

A

In-degree: The number of edges which terminate at v

Out-degree: The number of edges with v as their initial vertex

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

Let G = (V, E) be a graph with directed edges. Then,

A

|E| = Number of Out-degrees = Number of In-degrees

Because each edge has an initial vertex and a terminal vertex, the sum of the in-degrees and the sum of the out-degrees of all vertices in a graph with directed edges are the same

Both of these sums are the number of edges in the graph

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

Complete Graph on n vertices

A

Kn. The simple graph that contains exactly one edge between each pair of distinct vertices

No graph Kn is bipartite for n >= 2

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

Cycle Graphs, Cn

A

The edges loop. Visually, there is a hole in the graph.

The number of vertices must be even for the graph to be bipartite

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

Wheel graphs, Wn

A

Like Cn, But there is a vertex in the middle, with all other surrounding vertices connecting to it

The number of vertices must be odd for the graph to be bipartite

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

n-Cube Graphs, Qn

A

A graph with 2^n vertices representing all bit strings of length n, where there is an edge between 2 vertices that differ in exactly one bit position

No Qn can be bipartite

17
Q

What is a path

A

A sequence of n edges in a graph

18
Q

What is a circuit

A

A path that begins and ends on the same vertex

19
Q

When is a path/circuit simple?

A

If it doesn’t contain the same edge more than once

20
Q

What is a graph isomorphism?

A

If one graph is isomorphic to another (retains the same base structure)

21
Q

How to find a graph isomorphism between two graphs

A

Follow paths that go through all vertices so that the corresponding vertices in the two graphs have the same degree

22
Q

What is a connected graph?

A

An undirected graph is called connected if there is a path between every pair of vertices

An undirected graph that is not connected is called disconnected

We say that we disconnect a graph when we remove vertices or edges, or both, to produce a disconnected subgraph

23
Q

The strength of connection in directed graphs (strong and weak)

A

Strongly connected: There is a path from a to b and a path from b to a whenever a and b are vertices in the graph

Weakly connected: There is a path between every two vertices in the underlying undirected graph

24
Q

Connected component

A

A connected subgraph

25
Q

Euler Circuit

A

A simple circuit containing every edge of the graph

26
Q

Euler Path

A

A simple path containing every edge of G

27
Q

Hamiltonian path/circuit

A

A simple path/circuit that passes through every vertex exactly once

28
Q

Dirac’s Theorem

A

If G is a simple graph with n >= 3 vertices such that the degree of every vertex in G is >= (n/2), then G has a Hamilton circuit

29
Q

Ore’s Theorem

A

If G is a simple graph with n >= 3 vertices such that deg(u) + deg(v) >= n for every pair of nonadjacent vertices, then G has a Hamilton circuit

30
Q

Planar Graph

A

The graph can be drawn without any edges crossing

31
Q

Euler’s Formula

A

r = e - v + 2

32
Q

Corollaries (Euler’s Formula)

A

If G is a connected planar simple graph with e edges and v vertices, where v >= 3, then e <= 3v - 6

If a connected planar simple graph has e edges and v vertices with v >= 3 and no circuits of length three, then e <= 2v - 4

33
Q

How to calculate the number of unique hamilton paths/circuits on a complete graph?

A

(n-1)! / 2

34
Q

Euler’s Theorem

A

If a graph has more than two vertices of odd degree, then it cannot have an Euler path. If a graph is connected and has exactly two vertices of odd degree, then it has at least one Euler path (usually more). Any such path must start at one of the odd-degree vertices and end at the other one.