Discrete Structures Exam 3

Graphs and Induction

Formal Definition of a Graph

A collection of points connected by edges

Undirected graphs

Edges that connect to their vertices in both directions

Connected Graphs

For any two vertices in the graph, there is a path that connects them

How do you know when a directed graph is connected?

When the same graph, viewed as undirected, is connected

What is the degree of a vertex? What are the special descriptions for degrees of vertices in directed graphs?

The number of edges that are adjacent to the vertex, and vertices in a directed graphs can have an “in-degree” for the number of edges going out and an “out-degree” for a number of edges going in.

Definition of a loop

An edge from a vertex to itself

Definition of a subgraph

Let G = (V, E). If there exists a V’ and an E’ such that V’ is a subset of V and E’ is a subset of E, then G’ = (V’, E’) is defined as a subgraph of G

Definition of an induced subgraph

Let G = (V, E) and V’ be a subset of V. Let E’ be all the edges of E that only touch vertices in V’. Then, G’ = (V’, E’) is an induced subgraph of G, aka the subgraph induced by V’.

Definition of a Clique

A type of subgraph where every two vertices are connected by an edge, not a path

Definition of a walk

Let x, y be in V; a walk (or a path) from x to y is a sequence of vertices denoted by

x = x_0, x_1, x_2, …, x_k = y, where x_0 = x and x_k = y

such that (x_i, x_i+1 are in E) for i = 0, …, k-1

What is length of a walk equivalent to?

The number of edges between the vertices on the walk

What is one graph that is always found in the subgraphs of a graph?

The empty graph

Definition of a complete graph

When every vertex in a graph is connected to every other vertex with an edge;

For every vertex v_i in V, there exists an edge (v, v_k) where k does not equal i in E

When is a graph planar?

When it can be drawn in two-dimensions without any edges crossing

What is the maximum number of edges a planar graph can have when n>=3? (Theorem)

A planar graph with n>=3 edges can have at most 3n-6 edges

Definition of a simple circuit/cycle

A simple circuit starting at x in V is a sequence of vertices

x = x_0, x_1, …, x_k = x such that (x_i, x_i+1) in E for all i = 0, 1, 2, …, k-1

and x_i does not equal x_j except for x_0 = x = x_k

“It does not cross itself/repeat vertices”

Definition of a Hamiltonian Circuit

A simple circuit that visits each vertex in G exactly once

Definition of a Hamiltonian Graph

A graph that contains a Hamiltonian circuit

How do you know if a complete graph is Hamiltonian?

When it has n>=3

Definition of a bipartite graph

Given G = (V, E), if V can be divided into groups U and W such that:

For every u in U, there exists an edge (u, w) where w is in W

For every edge (u, x) where u in U, x is not in U

For every edge (w, x) where w in W, x not in W

Theorem connecting simple circuits, planar graphs, and max number of edges

Let L be the length of the shortest simple circuit in G. If 3 <= L <= infinity, then G has at most

max{(L/L-2) * (n - 2), n - 1} edges

How can you find the number of walks between two vertices (i, j) with a specific length?

Raise the adjacency matrix to the nth power and view the (i, j) position in the matrix

Formal and Informal Definition of a Sequence

Formal: A function from a range of the set of all integers to a set of objects

Informal: An ordered list of objects/elements/terms

Can sequences have repeated elements?

Yes

When a problem asks for an explicit definition of a sequence, what is it asking for?

A formula, sometimes with bounds (example, the sequence of positive even numbers can be defined as e_k = 2k where k > 0)

Properties of Summations

Let m <= n. Given two sequences a_i and b_i that start at m and end at n:

The separate summations added together equals the summation of a_i + b_i

A scalar constant can be inside or outside the summation

The product of two product summations of a_i and b_i equals the product summation of a_i * b_i

Go draw the ladder for induction vs strong induction and what terms are included in the inductive hypothesis