Discrete Structures: Graph Theory

• The notes corresponds to a Discrete Structure for Computer Science course

Graph Theory Basics

• The difference between the order of a graph and the size of a graph:
• Order: The number of vertices in the graph
• Size: The number of edges in the graph
• Cartesian product of sets A={1,2} and B={a,b} is A x B = {(1,a), (1,b), (2,a), (2,b)}
• Incidence matrix for a graph represents the relationship between vertices and edges
• Rows represent vertices
• Columns represent edges
• Entries indicate if a vertex is incident to an edge (usually 1 for incident, 0 for not)
• Relationship between total in-degree, out-degree, and total number of edges in a graph:
• The sum of in-degrees equals the sum of out-degrees
• Both are equal to the total number of edges in the graph
• A complete graph is a graph where every pair of distinct vertices is connected by a unique edge
• To identify if a graph is complete, check if every possible edge exists

Functions and Relations

• Let X= {1,3,5} and Y= {s, t, u,v}, and a function f: X -> Y is defined by the diagram
• The inverse image of S (assuming S = {s}): It's the set of elements in X that map to s
• From the diagram, f(1) = s, so the inverse image of s is {1}
• Range of f: The set of all output values of f
• This is {s, t, u}
• Domain of f: The set of all input values of f, which is X = {1, 3, 5}
• Co-domain of f: The set Y = {s, t, u, v}
• Values of f(1), f(3), f(5)
• f(1) = s
• f(3) = t
• f(5) = u
• If E= {x | x is an odd prime number, x∈N}, then E' (complement of E) consists of all natural numbers that are not odd prime numbers
• E' includes even numbers, 1, composite odd numbers, and 0 if N includes 0
• Given a set A={1,2,3}, consider the following relations: R= {(1,1),(1,2),(1,3),(3,3)}, S={(1,1),(1,2),(2,1),(2,2),(3,3)}, T= {(1,1),(1,2),(2,2),(2,3)}
• Reflexive: A relation is reflexive if (a,a) ∈ R for all a ∈ A
• R is not reflexive because (2,2) is missing
• S is reflexive because (1,1), (2,2), and (3,3) are present
• T is not reflexive because (3,3) is missing
• Symmetric: A relation is symmetric if (a,b) ∈ R implies (b,a) ∈ R for all a, b ∈ A
• R is not symmetric because (1,2) ∈ R but (2,1) ∉ R
• S is symmetric because for every (a,b) ∈ S, (b,a) ∈ S as well
• T is not symmetric because (1,2) ∈ T but (2,1) ∉ T
• Transitive: A relation is transitive if (a,b) ∈ R and (b,c) ∈ R implies (a,c) ∈ R for all a, b, c ∈ A
• R is not transitive because (1,2) ∈ R and (2,x) ∉ R for any x, but (1,x) exists
• S is not transitive because (1,2) ∈ S and (2,1) ∈ S, but (1,1) ∈ S (should be in relation for it to be transitive)
• T is not transitive because (1,2) ∈ T and (2,3) ∈ T, but (1,3) ∉ T
• Antisymmetric: A relation is antisymmetric if (a,b) ∈ R and (b,a) ∈ R implies a = b for all a, b ∈ A
• R is not antisymmetric because (1,2) ∈ R
• S is not antisymmetric because (1,2) ∈ S and (2,1) ∈ S, but 1 ≠ 2
• T is antisymmetric because the only pairs (a,b) and (b,a) are when a=b

Logic

• De Morgan's Laws involve negating conjunctions and disjunctions
• (¬(P ∧ Q) ≡ (¬P ∨ ¬Q)
• ¬(P ∨ Q) ≡ (¬P ∧ ¬Q)
• Truth table construction: List all possible combinations of truth values for P and Q (True/False), then evaluate both sides of the equivalence to confirm they yield the same truth values
• Expressing "Some professors are not strict" in symbolic logic:
• ∃x (Professor(x) ∧ ¬Strict(x))
• This means "There exists an x, such that x is a professor and x is not strict."
• Analyzing the logical nature of statements to determine if they are tautologies, contradictions, or neither:
• Determine if a statement is always true (tautology) or always false (contradiction)
• (~p) ∧ (p ∨ q) -> q : Neither
• (~q) ∨ (p ∧ q) -> q : Neither
• (p -> q) ∧ (q -> p) : Neither
• (q -> p) ∨ ~(p -> q) : Tautology

Graph Representations and Properties

• To find the complement of a graph:
• Start with the complete graph having the same vertices
• Remove the existing edges from the original graph - Add the edges that were missing from the original graph
• Adjacency matrix and adjacency list for a graph:
• Adjacency Matrix: A square matrix where the entry at row i, column j is 1 if there is an edge from vertex i to vertex j, and 0 otherwise
• Adjacency List: A list of vertices, where each vertex is associated with a list of its adjacent vertices. Lists the neighbours of each vertex
• Drawing a graph from an incidence matrix:
• Rows represent vertices
• Columns represent edges
• Examine the 1s in each column to determine which vertices that edge connects
• Making a graph from adjacency matrices and checking if it's a simple graph or multigraph:
• Simple Graph: Has no loops (edges from a vertex to itself) and no multiple edges (more than one edge between two vertices). The adjacency matrix will have 0s on the diagonal and only 0s or 1s elsewhere
• Multigraph: Allows multiple edges between the same pair of vertices. The adjacency matrix can have entries greater than 1

Linear Algebra and Graph Theory

• Finding Eigenvalues and Eigenvectors for a matrix (example matrix A):
• Eigenvalue: A scalar λ such that A * v = λ * v for some non-zero vector v
• Eigenvector: A non-zero vector v that satisfies A * v = λ * v, where A is a matrix and λ is an eigenvalue
• Finding Eigenvalues:
• Solve the characteristic equation det(A - λI) = 0, where I is the identity matrix. The solutions λ are the eigenvalues
• Finding Eigenvectors:
• For each eigenvalue λ, solve the system of linear equations (A - λI) * v = 0 for the eigenvector v
• This typically involves row-reduction to find the null space of (A - λI)
• Each eigenvalue has a corresponding eigenvector (or a set of eigenvectors forming an eigenspace)