CSC226 Unit 3 Vocab

reflexive

if all nodes have self loops

irreflexive

if no nodes have self loops

transitive

if x implies y and y implies z, then x needs to imply z too.

self loops only required if relation is a cycle

symmetric

if relation has bidirectional arrows. every pointing arrow needs its reverse.

antisymmetric

relation cannot have bidirectional arrows. two nodes cannot point at eachother. self loops are allowed.

asymmetric

relation cannot have bidirectional arrows. two nodes cannot point at eachother. self loops are not allowed

equivalence relation

when the relation is reflective, transitive, symmetric

poset

when the relation is reflexive, transitive, antisymmetric

degree of a node

how many edges are connected to the node

closed walk

walk that starts and ends on same node

open walk

walk that starts and ends on different nodes

trail

open walk that cannot visit edges twice

start and end on diff nodes

circuit

closed walk that cannot visit edges twice

start and end on the same node

path

trail that cannot visit the same node twice

cycle

circuit that cannot visit the same nodes twice except for first=last

euler’s trail

trail that visits every edge in a graph

this exists ONLY if there are exactly two nodes with an odd degree

euler’s circuit

circuit that visits every edge in a graph

euler’s circuit exists ONLY if all nodes have even degree

hamiltonian path

path that visits every node

starts and ends on diff nodes

hamiltonian cycle

cycle that visits every node

start and end on same node

depth first search

going down each branch before backtracking.

goes deep before wide

breadth first search

visits all neighbors at current branch before going deeper.

goes wide before deep

kruskal’s algorithim (for MSTs)

pick the cheapest edges first if it doesn’t start a cycle. starts w/ vertices and adds cheapest branch one by one.

need to reach all nodes w minimal and cheap edges

prim’s algorithim

grow from a starting vertex locally, choose the smallest edge that connects a vertex in the MST

need to reach all nodes w minimal and cheap edges

dijkstra’s algorithim

find the shortest path from one starting vertex to all other vertexes in a weighted graph.