Exam 2 Flashcards

(73 cards)

1
Q

construct zero-one matrices representing binary relations,

A
A matrix in which if the binary relation is true = 1, if false = 0
MR =
0 1 1
1 1 0
1 0 1
How well did you know this?
1
Not at all
2
3
4
5
Perfectly
2
Q

construct zero-one matrices representing union of binary relations R1 ∪ R2. (Join)

A

All relations that are in R1 and R2 are true = 1, and the others are 0

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

construct zero-one matrices representing the intersection of binary relations R1 ∩ R2 (Meet)

A

All relations that are in R1 that are also in R2 are true = 1, and the others left over in R2 are 0

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

onstruct zero-one matrices representing the composition of binary relations M1 O M2

A

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)}.

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

construct zero-one matrices representing the powers of a binary relation R^2

A

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

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

Multiplying Matrices

A

tbf

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

find the corresponding binary relation to the given zero-one matrix

A

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

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

construct directed graphs representing the given binary relations and vice versa

A

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

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

Determine whether a relation is reflexive when it is represented as a a zero-one matrix or a directed graph

A
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

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

Determine whether a relation is symmetric when it is represented as a a zero-one matrix or a directed graph

A
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

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

Determine whether a relation is antisymmetric when it is represented as a a zero-one matrix or a directed graph

A

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

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

Determine whether a relation is transitive when it is represented as a a zero-one matrix or a directed graph

A

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

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

Find reflexive closures of a binary relation

A

The reflexive closure of a relation R on A is obtained by adding (a, a) to R for each a ∈ A.

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

Find symmetric closures of a binary relation.

A

The symmetric closure of R is obtained by adding (b, a) to R for each (a, b) ∈ R.

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

Find transitive closure of a binary relation using Algorithm 1

A

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
How well did you know this?
1
Not at all
2
3
4
5
Perfectly
16
Q

Find transitive closure of a binary relation using Warshall’s algorithm

A

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...
How well did you know this?
1
Not at all
2
3
4
5
Perfectly
17
Q

Is the given relation an equivalence relation?

A

is reflexive, symmetric, and transitive.

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

What is the equivalence class of a set for the given equivalence relation?

A

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.

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

Find the partition of a set when an equivalence relation is given and vice versa

A

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))

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

Is the given relation a partial order or total order?

A

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

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

Find the ordering of given n-tuples according to the given lexicographic order.

A

(use curvy) < to order things by least to greatest usually

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

construct Hasse diagram for partial orderings

A

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

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

Find the following from a given poset or a Hasse diagram:

Maximal/minimal elements

A

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

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

Find the following from a given poset or a Hasse diagram:

The greatest/least element if exists

A

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.

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
25
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
26
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
27
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
28
Is the poset a lattice?
Every two elements will have a least upper bound and greatest lower bound.
29
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 <)
30
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.
31
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
32
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
33
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
34
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.
35
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.
36
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.
37
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.
38
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 ----------------------- (2*3)+(3*0)+(4*1) = 10 = (1,1)
39
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.
40
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.
41
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.
42
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
43
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)
44
Use Euler’s formula for a simple, connected, planar graph
Euler’s Formula: | regions = edges − vertices + 2.
45
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.
46
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
47
Understand Four Color Theorem.
The chromatic number of a planar graph is no greater than four.
48
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.
49
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
50
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.
51
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.
52
``` 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
53
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
54
Comparable
If X is a partial ordering on P or P is a partial ordering on X
55
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.
56
A simple graph G = (V, E)
Has no edges no loops and cannot have multiple edges joining vertices
57
Multigraphs
Like simple graphs, but there may be more than one edge connecting two given nodes.
58
Pseudographs
Like multigraphs, but edges connecting a node to itself are allowed (i.e. loops are allowed)
59
Simple Directed Graph
Like a simple graph but with arrows
60
Directed Multigraph
Like a simple directed graph but there may be more than one edge connecting two given nodes and loops are allowed.
61
Complete graphs
contains exactly one edge between each pair of distinct vertices.
62
Cycles
Graphs that have edges that do not cross
63
Wheels
A cycle that has a vertex in the middle where all outside vertices connect to
64
n-cubes
Two vertices are adjacent if and only if the bit strings that they represent differ in exactly one bit position
65
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).
66
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.
67
Graph Union
Join like vertices together to create a joined graph
68
isolated vetices
if the vertices degree is 0
69
pendant vertices
if the vertices degree is 1
70
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.
71
simple paths
when a path never repeats an edge
72
s not strongly connected nor weakly connected
if the graph is not connected
73
handshaking theorem
2(edges) = sum of degrees,