Exam 2 Flashcards
construct zero-one matrices representing binary relations,
A matrix in which if the binary relation is true = 1, if false = 0 MR = 0 1 1 1 1 0 1 0 1
construct zero-one matrices representing union of binary relations R1 ∪ R2. (Join)
All relations that are in R1 and R2 are true = 1, and the others are 0
construct zero-one matrices representing the intersection of binary relations R1 ∩ R2 (Meet)
All relations that are in R1 that are also in R2 are true = 1, and the others left over in R2 are 0
onstruct zero-one matrices representing the composition of binary relations M1 O M2
Is the zero-one matrix for the composite
of R1 and R2, R2 ◦ R1.
(a, c) is in R2 ◦ R1 if (a, b) ∈ R1 and (b, c) ∈ R2.
Example of composition
Question 1: Let A = {a, b, c}, B = {1,2} and C = {a, b, g} is being three sets and R = {(a, 1), (a, 2), (b, 2), (c, 1)} and S = {(1, a), (2, b), (2, g)} be two relations, find SoR.
Solution:
Here, R is a relation where a goes to 1 and so on. Thus, S o R will be calculated as a goes to 1 and in turn, 1 goes to a, yielding (a, a).
Hence, SoR = {(a, a), (a, b), (a, g), (b, b), (b, g), (c, a)}.
construct zero-one matrices representing the powers of a binary relation R^2
Is the zero one matrice multiplied by itself
ex.
(0∧0)∨(1∧1)∨(1∧1)(0∧1)∨(1∧1)∨(1∧0)(0∧1)∨(1∧0)∨(1∧1)
(1∧0)∨(1∧1)∨(0∧1)(1∧1)∨(1∧1)∨(0∧0)(1∧1)∨(1∧0)∨(0∧1)
(1∧0)∨(0∧1)∨(1∧1)(1∧1)∨(0∧1)∨(1∧0)(1∧1)∨(0∧0)∨(1∧1)
=
1 1 1
1 1 1
1 1 1
Multiplying Matrices
tbf
find the corresponding binary relation to the given zero-one matrix
the y axis on the matrix is the first coordinate, the x axis is the second. If = 1, then those coordinates are in the binary relation
construct directed graphs representing the given binary relations and vice versa
Directed graphs are the graphs that point to one another, if there is a relation (a,b) then a has an arrow pointing to b
Determine whether a relation is reflexive when it is represented as a a zero-one matrix or a directed graph
ZO Matrix: In other words, all elements are equal to 1 on the main diagonal. = 100 010 001
digraph:
When all points have self loops
Determine whether a relation is symmetric when it is represented as a a zero-one matrix or a directed graph
ZO Matrix: Mij = Mji for all i and j. for every (a,b) there must be a (b,a)
digraph:
When there are arrows point going in both directions for all points
Determine whether a relation is antisymmetric when it is represented as a a zero-one matrix or a directed graph
ZO Matrix:
R is antisymmetric if and only
if Mij = 0 or Mji = 0 for all i does not equal j.
Except for self loops, Mij and Mji cannot both equal 1
digraph:
When there are no points in which arrows point in between one another
Determine whether a relation is transitive when it is represented as a a zero-one matrix or a directed graph
ZO Matrix & digraph
Must be able to get from A to D and back to A with A,C & C,D and then D,A
Find reflexive closures of a binary relation
The reflexive closure of a relation R on A is obtained by adding (a, a) to R for each a ∈ A.
Find symmetric closures of a binary relation.
The symmetric closure of R is obtained by adding (b, a) to R for each (a, b) ∈ R.
Find transitive closure of a binary relation using Algorithm 1
Transitive Closure
=MR∗
= MR ∨ MR^2 ∨ MR^3 ∨ M^4
You take the column from the first matrix and figure if its true for all elements of the row of the other matrix
= 0 1 0 0 1 0 1 0 0 0 0 1 1 0 0 0 ∨ 1 0 1 0 0 1 0 1 1 0 0 0 0 1 0 0 ∨ 0 1 0 1 1 0 1 0 0 1 0 0 1 0 1 0 ∨ 1 0 1 0 0 1 0 1 1 0 1 0 0 1 0 1 = 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1
Find transitive closure of a binary relation using Warshall’s algorithm
Add 1 to positons in which paths within the poset use as an interior vertex
ex. W1 = 1 for all paths that use 1 as an interior vertex so if (b,a) and (a,d) exists, add 1 in (b,d) and so on...
Is the given relation an equivalence relation?
is reflexive, symmetric, and transitive.
What is the equivalence class of a set for the given equivalence relation?
The set of all elements that are related to an element
a of A is called the equivalence class of a. The equivalence class of a with respect to R is denoted
by [a]R.
Find the partition of a set when an equivalence relation is given and vice versa
A partition is all the different ways to create subsets that include all elements in a set (nonempty (is not empty), disjoint (contain duplicates of an element) and exhaust (use every element))
Is the given relation a partial order or total order?
Is a partial order if partial order if it is reflexive, antisymmetric, and transitive.
A total order is If S is a poset and every two elements of S are comparable
Find the ordering of given n-tuples according to the given lexicographic order.
(use curvy) < to order things by least to greatest usually
construct Hasse diagram for partial orderings
Construct a digraph representation of the poset (S, 4) so that all edges point up (except the loops)
• Eliminate all loops
• Eliminate all edges that are redundant because of transitivity
• Eliminate the arrows at the ends of edges since everything points up
Find the following from a given poset or a Hasse diagram:
Maximal/minimal elements
Minimal Elements:
The elements at the bottom that have no other elements related to them
Maximal Elements:
The elements that are at the top that are not related to any other elements
Find the following from a given poset or a Hasse diagram:
The greatest/least element if exists
Least Element:
element would have to be a number that relates to all other elements
Greatest Element:
element would have to be a number that all other
elements relate to.
Find the following from a given poset or a Hasse diagram:
Upper/lower bounds of a subset
Upper Bound:
If you were to pick any elements in the poset, the upperbound would be the elements that all of the inital elements chosen relate to
Lower Bound:
If you were to pick any elements in the poset, the lowerbound would be the elements that relates to the greatest upperbound
Find the following from a given poset or a Hasse diagram:
The least upper bound if exists
Within the set of all upperbounds, the element that relates to all other upperbounds is the least upperbound
Find the following from a given poset or a Hasse diagram:
The greatest lower bound if exists
Within the set of all lowerbounds, the element that to all other lowerbounds relate to is the least upperbound
Is the poset a lattice?
Every two elements will have a least upper bound and greatest lower bound.
Extend a partial ordering on a finite set to a total ordering by doing a topological sort.
ex. Find an ordering of the tasks of a software project if the Hasse diagram for the tasks of the project
is shown. (use the curvy <)
poset
A set S together with a partial ordering R is called a partially ordered set, or poset, and is denoted
by (S, R) or (S, partial ordering R ).
Members of S are called elements of the poset.
Represent graphs using adjacency lists, adjacency matrices, and incident matrices,
and convert between them.
adjacency lists = table w/ vetercies/ adjacent vetices
initial vetices/terminal vertices
adjaency matrices = element = 1 when two points are adjacent, in somecases can = 2 or 3 depending on the degree of vertex
incident matrices= matrix clearly labeled with a-d and e1-…en in which in each column en, element =1 if a-d make up the relation
Understand invariant properties with respect to graph isomorphism.
Properties preserved by isomorphism of graphs.
• must have the same number of vertices
• must have the same number of edges
• must have the same number of vertices with degree k
• for every proper subgraph g of one graph, there must be a proper subgraph of the other graph
that is isomorphic of g
Prove that two given graphs are isomorphic or give a reason why they are not.
c if there exists a one-to-one
and onto function f from V1 to V2 with the property that a and b are adjacent in G1 if and only if
f(a) and f(b) are adjacent in G2, for all a and b in V
Connectedness in undirected and directed graphs.
connected if there is a path between every pair of distinct vertices
of the graph. An undirected graph that is not connected is called disconnected.
Be able to find cut vertices and cut edges.
Cut vertices are vertices that produce a subgraph with more connected components when removed
from a graph (and all incident edges to it)
Cut edges or bridges are edges that produce a subgraph with more connected components when
removed from a graph.
Be able to find connected components of a graph or weakly and strongly connected
components of a directed graph.
Strongly Connected:
That from any element a you can get to any element b in the graph
Weakly Connected:
A directed graph is weakly connected if there is a path between every two vertices in the underlying
undirected graph.
Use paths to prove or disprove that the two given graphs are isomorphic.
The connectedness and the existence of a circuit or simple circuit of length k are graph invariants
with respect to isomorphism. The existence of a simple circuit of a particular length can be used
to show that two graphs are not isomorphic.
Find the number of paths of arbitrary length. (Theorem 2)
Just multiply the adjanceny matrix to the nth power and look at whatever position needed to find the number of paths of length n.
To multiply adjaceny matrices, you take the row of the first matrix and the column of the second, and you multiply the like position and add them together to get the new value
row (1)= 2 3 4
column(1) = 3 0 1
———————–
(23)+(30)+(4*1) = 10 = (1,1)
Understand the Euler circuits/paths and Hamiltonian circuits/paths problems and
how they are different
Euler Circuit:
An Euler circuit in a graph G is a simple circuit containing every edge of G.
Euler Path:
An Euler path in G is a simple path containing every edge of G
Hamilton Circuit:
A Hamilton circuit is a simple circuit that traverses every vertex in G exactly once.
Hamilton Path:
A Hamilton path is a simple path that traverses every vertex in G exactly once.
Test a graph for the existence of an Euler circuit or Euler path and find one if exists.
Theorem 1:
A connected multigraph with at least two vertices has an Euler circuit if and only if each of its
vertices has an even degree.
Theorem 2:
A connected multigraph has an Euler path but not an Euler circuit if and only if it has exactly two
vertices of odd degree.
Determine whether there exists a Hamilton circuit or Hamilton path and find one if
exists.
Dirac’s Theorem:
If # of vertices ≥ 3 such that
the degree of every vertex in G is at least half the total # of vertices, then G has a Hamilton circuit
Ore’s Theorem:
If # of vertices ≥ 3 such that
deg(u) + deg(v) ≥ # of vertices for every pair of nonadjacent vertices, then G has a Hamilton circuit.
Find a shortest path and the length of the path between two vertices in a simple,
weighted, connected graph using Dijkstra’s algorithm – should be able to show all
intermediate steps.
To find a->z
create table :
A-> B C D Z
A 2 5 in in since B is least it will be next row
B X 2 7 in X means already went there, C
C X X 9 2 Z is lowest
So path is a,b,c,z
Determine whether or not a graph is planar.
A graph is called planar if it can be drawn in the plane without any edges crossing (where a
crossing of edges is the intersection of the lines or arcs representing them at a point other than their
common endpoint)
Use Euler’s formula for a simple, connected, planar graph
Euler’s Formula:
regions = edges − vertices + 2.
Understand the concept of the coloring of a graph.
A coloring of a simple graph is the assignment of a color to each vertex of the graph so that no
two adjacent vertices are assigned the same color.
Understand the connection between coloring maps and coloring graphs
o Construct a dual graph of a map
see example of how to make the picture graph correlate with the simple graph
Understand Four Color Theorem.
The chromatic number of a planar graph is no greater than four.
Find the chromatic number of a graph
The chromatic number of a graph is the least number of colors needed for a coloring of this graph.
Solve problems by transforming them to graph coloring problems.
1-first draw the intersection graph of the given sets.
2-Figure out the least amount of color needed for each vertex so that no colors are adjacent
3- The amount of colors used can be used to determine the number of times something happens
example of finding nonzero entries
How many nonzero entries does the matrix representing the relation R on A = {1, 2, 3, . . . , 100}
consisting of the first 100 positive integers if R is
a {(a, b)|a > b}?
We’ll start from the bottom of the matrix. We know that that 100 is greater than 99 positive
integers. We also know that 99 is greater than 98 positive integers. Following this line of
thought, it’s easy to see that the total number of elements is:
99 + 98 + . . . + 1 = 99(99 + 1)/2 = 4950.
connectivity relation R*
consists of the pairs (a, b) such that
there is a path of length at least one from a to b in R.
What is the congruence class [n]5 (that is, the equivalence class of n with respect to congruence
modulo 5) when n is
[2]5 = {i|i ≡ 2 (mod 5)} = {. . . , −8, −3, 2, 7, 12, . . .}Just equals 2 a set containing 2 + 5
Let X = {1,2,3,4,5,6} and P = {(1,1), (2,2), (3,3),
(4,4), (5,5), (6,6), (6,1), (6,4), (1,4), (6,5), (3,4),
(6,2)}. X is a partial ordering on P if:
P is a partial order: reflexive, antisymmetric, and transitive
Comparable
If X is a partial ordering on P or P is a partial ordering on X
Well-Ordered Set
is a well-ordered set if it is a poset such that it is a total ordering and every nonempty subset
of S has a least element.
A simple graph G = (V, E)
Has no edges
no loops
and cannot have multiple edges joining vertices
Multigraphs
Like simple graphs, but there may be more than one edge connecting two given nodes.
Pseudographs
Like multigraphs, but edges connecting a node to itself are allowed (i.e. loops are allowed)
Simple Directed Graph
Like a simple graph but with arrows
Directed Multigraph
Like a simple directed graph but there may be more than one edge connecting two given nodes and
loops are allowed.
Complete graphs
contains exactly one edge between each pair of distinct vertices.
Cycles
Graphs that have edges that do not cross
Wheels
A cycle that has a vertex in the middle where all outside vertices connect to
n-cubes
Two vertices are adjacent if and only if the bit strings that they represent differ in exactly one bit position
Bipartite Graphs
partitioned into two disjoint sets V1
and V2 such that every edge in the graph connects a vertex in V1 and a vertex in V2 (so that no edge
in G connects either two vertices in V1 or two vertices in V2).
Complete Bipartite Graphs
partitioned into two subsets of m
and n vertices, respectively with an edge between every pair of vertices if and only if one vertex in
the pair is in the first subset and the other vertex is in the second subset.
Graph Union
Join like vertices together to create a joined graph
isolated vetices
if the vertices degree is 0
pendant vertices
if the vertices degree is 1
neighborhood
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.
simple paths
when a path never repeats an edge
s not strongly connected nor weakly connected
if the graph is not connected
handshaking theorem
2(edges) = sum of degrees,
