Graphs and Relations

Relations §

• set of ordered pairs
• has domain set and range set
• common domain and range

Properties §

• reflexive
  • $(x,x)$ is in relation for all $x$ in domain
• symmetric
  • if $(x,y)$ is in relation, then $(y,x)$ is also in relation
• antisymmetric
  • if $(x,y)$ is in relation, then $(y,x)$ is not in relation
• transitive
  • if $(x,y)$ and $(y,z)$ are in relation, then $(x,z)$ is also in relation

Equivalence Relation §

• reflexive
• symmetric
• transitive

Partial Order §

• reflexive
• antisymmetric
• transitive

Total Order §

• same as partial order but
• for any $x,y$, either $(x,y)$ is a relation or $(y,x)$ is a relation

Graphs §

• vertices and edges
• can be directed and undirected
• can be expressed by relations