Graph

A graph $G= (V, E)$ is a pair of sets $(V, E)$ where $V$ is a set of vertices and $E$ is a set of edges.

If $E$ $E$ is a set of unordered pairs, the graph is called undirected. If $E$ $E$ is a set of ordered pairs, the graph is called directed.
- self-loop does not allowed in undirected graph (in csc236/csc263)
Weight of edge is a function $w : E \to \R$ where $w(\{u,v\})$ is the weight of edge $\{u,v\}$
A matching $M\subseteq E$ $M \subseteq E$ is a subset of edges that those edges that do not share any end points
- every vertex in one matching then this matching is perfect
two vertices $u,v$ $u, v$ are adjacent if $\{u,v\}\in E$ ${u, v} \in E$
- one is called neighbor of the other
- an edge (u,v) is incident on vertices u and v. In a directed graph, the terminology differentiates between the beginning and ending vertex of an edge. So edge (u,v) which leaves vertex u is said to be incident from vertex u and is incident to (or enters) vertex v
A sequence of distinct vertices $(v_1,\ldots, v_n)$ $(v_{1}, \dots, v_{n})$ is a path from $v_1$ $v_{1}$ to $v_n$ $v_{n}$ if for every $i\in \{1,\ldots, n-1\}, v_i$ $i \in {1, \dots, n - 1}, v_{i}$ and $v_{i+1}$ $v_{i + 1}$ are adjacent.
- The length of the path is the number of edges in the path.
- A simple path contains no repeated edge
A sequence of distinct vertices $(v_1,\ldots, v_n)$ $(v_{1}, \dots, v_{n})$ is a the cycle if $(v_1,\ldots, v_n)$ $(v_{1}, \dots, v_{n})$ is a path, $v_1 = v_n$ $v_{1} = v_{n}$ and $\{v_{n-1}, v_n\in E\}$ ${v_{n - 1}, v_{n} \in E}$
- A cycle is called Hamiltonian if every vertex appear in the cycle exactly once (except for the start/end vertex which appears twice)
- A simple circle contains no repeated edge
A $k$ -(vertex) coloring of $G$ is a function $f: V\to C$ , $\forall u,v \in V, \{u,v\}\in E \lor \{v,u\}\in E \implies f(u) \ne f(v)$
Connected: $\forall u,v \in V, v\ne u$ there is some path from $u$ to $v$
acyclic: no cycle in graph
independent set: $I \subseteq V$ , $\forall v,u\in I, \nexists e\in E, e = \{v,u\}\lor e=\{u,v\} \implies I$ is an independent set
In an undirected graph, the degree of a vertex $\nu$ is the number of edges incident on $\nu$ . In a directed graph, the in-degree of vertex $\nu$ is the number of edges incident to $\nu$ (the size of set $\{(x,\nu):x\in E\}$ ) and the out-degree is the number of edges incident from v (the size of set $\{(\nu,x):x\in E\}$ ).
A connected component is a group of nodes that are connected by edges

Tree: a graph are connected and acyclic

Trees $\iff$ minimally connected graph aka remove any edge will cause disconnect
Trees $\iff$ maximally acyclic graph aka add any edge will cause cycle
$\forall u,v\in V, u\ne v \implies$ unique path from $u$ to $v$
Free tree is used for an undirected connected acyclic graph without a specific vertex designated as the root.
Rooted tree with one vertex is designated as the root.

A forest is a collection of (0+) disjoint trees

A tree is also a forest.
Total vertices - Total Edges = # trees

Binary Tree: a tree that every vertex has at most two edges incident to it.

Some examples about Graph:

locations on maps, relationship between people(contact facing), Courses, WIFI Connection, Trees, vector graph, airport routes, functions, binary relations

Matching Problem:

input: a graph with weight
output: A matching (usually maximum/minimum)

Pathing Finding Problem:

Input: a graph and two vertices
output: A path between two vertices

Travelling Salesman Problem:

Input: a graph and a start vertex
Output: a Hamiltonian cycle minimizes the total edge weights

Coloring Problem:

input: a graph
output a k-coloring of the graph

Independent Set Problem:

input: a graph, a number $k\in \N$ with $k>1$
output: An independent set $I \subseteq V\in G$ of size $k$

We also talked more about graph on csc263