Week 12: Graphs and Trees

Question 1

graphs/simple graphs basics

Answer 1

• simple graphs are referred to as a graph
• graphs consists of a set of vertices and a set of edges
• edge is an unordered pair of verticies
• applications label the vertices and edges with data

Question 2

simple graph

Answer 2

• a simple graph has no loops and no multiple edges
• no two edges connect the same pair of vertices
• each edge connect two different vertices

Question 3

multigraphs/psuedographs

Answer 3

• multigraph have multiple edges connecting the same two vertices
• a pseudo graph incudes loops, as well as multiple edges connecting the same pair of vertices

Question 4

endpoints

Answer 4

• the vertices of an edge
  ex. if edge u is connected to a and b, a and b are its endpoints)

Question 5

incident

Answer 5

• an edge and its endpoints
• ex. if u has vertices a and b, u and a are incident

Question 6

adjacent

Answer 6

• the endpoints of an edge
• ex. endpoints a and b of u are adjacent

Question 7

neighbor

Answer 7

• an adjacent vertex
• ex. c and d are both endpoints of an edge, so they are neighbors

Question 8

vertex degree

Answer 8

• the number of neighbors a vertex has
• ex. if c is connected to 3 vertices by edges (w/o other vertexes between them) then its vertex degree is 3

Question 9

nodes/links

Answer 9

• nodes are another term for vertices
• links are another term for edges

Question 10

neighborhood of a vertex

Answer 10

• the set of all neighbors of a vertex v of G = (V, E) denoted by N(v) is the neighborhood of v
• if A is a subset of V, we denote by N(A) the set of all vertices in G that are adjacent to at least one vertex in A
• so, N(A) = U_v ∈ A N(v)

Question 11

handshake theorem

Answer 11

• the sum of the degrees of the vertices equal twice the number of edges
  ∑ deg(v) = 2 |E|
  v ∈ V

Question 12

if a graph has 5 vertices, can each vertex have degree 3?

Answer 12

• no, because by the handshake theorem, the sum of the degree is 15, which is odd
• must have a whole number of edges

Question 13

representing graphs as matrices

Answer 13

• a graph with n vertices can be a nxn matrix (mij = 1)
• the matrix is symmetric
• the space complexity is O(n^2)

Question 13

list representation

Answer 13

• a graph can also be represented with an array of edge lists, the ith element lists the vertices that are neighbors of v_i
• ex. ((2), (1, 3), (2, 4, 5), (3, 5), (3, 4))
• each element are vertices connected to one specific vertex
• the space complexity is O(m+n) for a graph with n vertices and m edges
• edge lists are generally good for sparse graphs and bad for dense graphs

Question 14

special types of graphs: complete graph k_n

Answer 14

• has edges between all pairs of vertices
• aka every vertex is connected to every other vertex

Question 15

special types of graphs: cycle graph c_n

Answer 15

• has n edges that form a closed simple curve
• ex. 4 vertices that make a normal square

Question 16

special types of graphs: wheel w_n

Answer 16

• a cycle graph plus a center vertex that is adjacent to the other vertices
• ex. simple square with one additional vertex in center

Question 17

n-dimensional hypercube h_n

Answer 17

• 2^n vertices representing to 2^n bit strings of length n
• n * 2^(n-1) edges, with two vertices being adjacent only when the bit strings they represent differ in exactly one bit position

Question 18

bipartite graphs

Answer 18

• a simple graph G is bipartite if V can be partitioned into two disjoint subsets V1 and V3 s.t. every edge in the graph connects a vertex in V1 and vertex in V2
• no edges connect two vertices in V1 OR in V2
• the pair (V1, V2) is called a bipartition of the vertex set V of G

Question 19

complete bipartite graph K_(m, n)

Answer 19

• is a graph that has its vertex set partitioned into two subsets m and n vertices, with an edge between two vertices iff one vertex is in the first subset and the other is in the second subset
• a matching is a subset of a bipartite graph in which every vertex has degree one

Question 20

directed graph basics

Answer 20

• a directed graph G = (V, E) consists of a set V of vertices and a set E of directed edges
• each edge is associated with an ordered pair of vertices
• the directed edge associated with the ordered pair (u, v) is said to start at u and end at v

Question 21

directed graphs terminology

Answer 21

• a directed graph has ordered pairs of vertices as edges
• the tail of ab is a and the head is b
• the matrix and edge list representations carry over

Question 22

directed graphs formula

Answer 22

• let G=(V, E) be a graph with directed edges
• then |E|= v∈V ∑ deg +(v) = v∈V ∑ deg -(v)
• the first sum counts the number of outgoing edges over all vertices
• the second sum counts. number of incoming edges over all vertices
• both equal # of graph edges

Question 23

paths definition

Answer 23

• a sequence of edges that begins at a vertex and travels from vertex to vertex along edges
• numerous problems can be modeled with paths

Question 24

path sequence representation/ when it's simple

Answer 24

- path of length k from vertex u to vertex v is a sequence of k edges e, .. ek with - e1=(u, x1), e2 = (x1, x2),.. e(k-1) = (x(k-1), xk) and xk = c - when the graph is simple, path is denoted by vertex sequence u, x1, x2, · · · , xk−1, v - The path is a circuit (cycle) if it begins and ends at the same vertex (i.e., u = v). - A path or circuit is simple if it does not contain the same edge more than once

Question 25

connectedness

Answer 25

- vertices a and be are connected if there is a path from a to b - a graph is called connected if every pair of vertices are connected - aka can make a path between one vertex to every other vertex

Question 26

connectedness components

Answer 26

- connection is an equivalence relation - symmetric (path from u to v, then path from v to u) - transitive (path from u to v AND path from v to w, then path from u to w) - the equivalence classes are called connected components

Question 27

Euler paths

Answer 27

a simple path containing every edge of a graph G

Question 28

euler circuits

Answer 28

- a simple circuit containing every edge of a graph G in a graph or multigraph exactly ONCE - every vertex must have an even degree

Question 29

condition for the existence of Euler circuits

Answer 29

- a connected multigraph G has a Euler circuit iff each of its vertices have even degree - if circuit enters a vertex via one edge, it must exit via another - means each visit to a vertex consumes 2 edges (one incoming, one outgoing)

Question 30

hierholzer's algorithm

Answer 30

- choose a starting vertex u - form a circuit c by following edges from u until returning to u - while there exists an edge vw with v in c and w not in c - form a circuit d starting from vw using edges not in c - the runtime is O(e) for a graph with e edges

Question 31

connected multigraphs and Euler paths

Question 32

Hamilton paths

Question 33

hamilton circuits

Question 34

condition for the existence of hamilton circuits

Question 35

Dirac's theorem

Question 36

Ore's theorem

Question 37

applications of hamilton circuits

Question 38

planar graphs definition

Question 39

Euler's formula

Question 40

corollary 1

Question 41

corollary 2

Question 42

corollary 3

Question 43

vertex coloring definition

Question 44

vertex coloring with special types of graphs

Question 45

dual graphs

Question 46

four color theorem

Question 47

directed graphs in and out degrees

Answer 47

- in-degree of vertex v, denoted deg-(v), is the number of edges which terminate at v - the out-degree of v, denoted deg+(v), is the number of edges with v as their initial vertex