Binary Relations and Graphs

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.

Equivalences and Orderings

Previously defined terms: (ir)reflexive, (anti)symmetric, (anti)transitive. What are some common, interesting combinations of these properties?

• Previously mentioned equality is reflexive, symmetric, and transitive? Similar relations?
• Equivalence classes
• Partitions

• What about properties for "less than"? "less than or equal"? "greater than"? "greater than or equal"?
• Partial order (poset) vs. Total order -- examples

Closures

• E.g., for natural numbers, "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 others
• Transitive closure vs. Reflexive and transitive closure
• Note: e.g., the transitive closure of any relation is transitive; the transitive closure of a transitive relation is the same relation.

Graphs

• Define: G=(V,E); vertices/nodes, edges/arrows -- pictures
  • Note: More generally, often wish to label vertices and/or edges with information. E.g., the "distance" between two vertices.
• Directed vs. undirected -- pictures and examples
• Some interesting properties of graphs: complete, acylic, connected, biconnected, isomorphic
  • Note: Later classes investigate algorithms for check whether graphs have such properties
• Some related notions: subgraph, connected components, biconnected components
  • Note: Later classes investigate algorithms to compute such things
• Representations: Edge list, Adjacency list, Adjacency matrix, Incidence matrix

Binary relations and graphs

• Can view either way -- examples
• Allows us to think about the same info in different ways.
  • E.g., if a relation is reflexive, what do we know about its graph?
  • E.g., consider a relation and its transitive closure. What is the relationship between the corresponding graphs?