Binary Relations and Graphs

Some of this should already be familiar. We'll quickly review, and focus on what's most important for CS.

Probably won't be able to cover all of these definitions and examples during class, but these are what I consider most important from the reading.

RST

(Previously covered in homework. Not repeating.)

Should be familiar with reflexive, symmetric, transitive

Always has the property	Never has the property	Doesn't always have the property
Reflexive	Irreflexive E.g., "is-married-to"	Not reflexive
Symmetric E.g., "is-married-to"	Antisymmetric E.g., "is-parent-of"	Not symmetric, asymmetric
Transitive E.g., "is-ancestor-of"	Intransitive	Not transitive

E.g., how to define symmetric, antisymmetric, and asymmetric using first-order logic?

The most important combinations of previous properties:

Equivalence relation
- Which properties?
- Similar relations?
- Equivalence classes
  - Some sample uses — minimizing DFAs, modular arithmetic, operational equivalence
  - An importance algorithmic concept — coalescing equivalence classes
- Partitions
What are the properties for "less than"? "less than or equal"?
- Same for "greater than", "greater than or equal", respectively
E.g., how to define ordering relations on 2D points?
- What properties do they have?
- An example of defining orderings on tuples/structures.
(Non-strict) Partial order
- reflexive, antisymmetric, transitive
- Examples?
- poset
(Non-strict) Total order
- reflexive, antisymmetric, transitive, total
- Totality on relations: R(a,b) or R(b,a), for each pair of elements
- Examples?
Strict …
- < vs. ≤
- Replace reflexive & antisymmetric with irreflexive & asymmetric
- irreflexive is redundant, given asymmetric

E.g., "is the successor to" and "is greater than" are closely related. So are "is the successor to" and "is greater than or equal to".
- Given the first relation, we can generate the other.
Transitive closure vs. Reflexive and transitive closure
- Compare closures for "is-parent-of"
- Note: e.g., the transitive closure of any relation is transitive; the transitive closure of a transitive relation is the same relation.

Define: G=(V,E); vertices/nodes, edges/arrows — pictures
Variations:
- Directed vs. undirected — examples
  - Edge set as a relation — Allows us to think about the same info in different ways.
  - Related to symmetry
- Label vertices and/or edges with information. E.g., distance, cost, supply/demand
- Allow self-edges or not
  - Related to reflexivity
- Multi-graphs — allow multiple edges between same pair of edges — esp. common when edges are labeled
Representations: Edge list, Adjacency list, Adjacency matrix, Incidence matrix
- Size of each representation?
- Efficiency of operations, e.g., how fast to add an edge?
- |E|=? — sparse vs. dense
- Same representations apply to relations
Some interesting properties of and notions with graphs: complete, acylic, DAG, subgraph, connected, connected components, biconnected components, isomorphic
- Note: Later courses investigate algorithms for check whether graphs have such properties
- Examples of usefulness
- Cycles can be annoying
- An important algorithmic concept — DFS on graphs
- What is the transitive closure of "has-edge-to"?