Lecture 6 | Myndbook

Graphs

Cartesian Product

AXB = { (a, b) | a E A and b E B }

Ordered and unordered pairs

{0, 1, 2 } unordered

(1, 2, 3) ordered

Definition

Mathematical structure for representing relationships (AKA nodes and edges)

Is a topological Sort

Ordering where no node is listed before its predecessors.

Equivalence Relations

Binary relation is called equivalent relation iff:

Symmetry

For any x E A and y E A, if xRy, then yRx.

Transitivity

For any x, y, z in A, if xRy and yRz, then xRz.

Reflexive

For any x E A, xRx.

Binary relations is a property of two objects are related in a similar way

aRb iff a is related to b byh the relation R.

Formally, a relation is a set of ordered pairs representing the pairs for which the relation is true. So, aRb = (a, b) E R.

Order relation

Relates orders of two elements.

Antisymmetric

Description