CS 241 Graphs and Trees

how many edges in a tree with n nodes

n-1

what differentiates a tree from a graph, in terms of path?

there’s a UNIQUE path to reach any node. no two paths can reach the same node.

is a tree a graph? is a graph a tree?

tree is a graph; graph is not a tree.

can a single vertex be a graph?

yes. also a tree i believe, with just the root node.

how are graphs represented (notation)?

G = (V, E) , where V and E are sets.

do trees have more vertices or edges?

more vertices.

how are edges represented mathematically (with vertices)? how does this differ in directed vs undirected graphs?

e = (v_i, v_j) ; in undirected graphs, this order does not matter (unordered pair) but in directed graph, the order determines (from, to) .

give the “incident” definitions of an edge e and vertices v and w BOTH ways. (also, what are v and w called with respect to each other?)

1. an edge e is incident on v and w. (it connects the two vertices)

2. vertices v and w are incident on e and they’re called adjacent vertices

formal definition of loop

an edge incident on a single vertex

parallel edges

same pair of vertices for two edges (regardless of ordered pair or not)

formal definition of an isolated vertex (using “incident”)

vertex not incident to any edge

connected graph formal definition

from any vertex, we can go to ALL other vertices

disconnected graph formal definition

collection of separate connected subgraphs/components

complete graph (notation, definition)

denoted k_n , is a graph with n vertices where there’s an edge between EVERY pair of distinct vertices. know how to draw k_1, k_2, k_3, k_4

bipartite graph definition

graph where set of vertices can be partitioned into two sets such that there’s NO edge between two vertices of the same sets.

color shortcut method

if we can color vertices of a graph such that no two adjacent vertices are the same colors, it is a bipartite graph. otherwise, it is a non bipartite graph.

how do we formally write on an exam that something is a bipartite graph?

“this is a bipartite graph because it can be split into two sets of vertices such that V_1 = {} V_2 = {}, and each edge of this graph is incident on one vertex in V_1 and another vertex in V_2”

how do we formally write on an exam that something is a NON bipartite graph?

“this graph is not bipartite because consider the vertices A, B, C. if A lies in V_1, then B should lie in V_2. since B lies in V_2, C should lie in V_1. but C cannot be placed in V_1 because there’s an edge from A to C”

what is a complete bipartite graph? (notation and definition)

a complete bipartite graph on m and n vertices, denoted as k_{m, n} , is a simple graph if the vertex set can be partitioned into two sets V_1 and V_2 such that each edge of the graph has one vertex in V_1 and the other in V_2, and each vertex in set V_1 is connected to every vertex in set V_2 by an edge.

cycle

unique path where we come back to the original node

euler’s cycle formal definition

path in a graph that travels every edge exactly once and comes back to the original node

euler’s cycle requirement

graph must be connected and every vertex should have an even degree. then it has an euler’s cycle, otherwise it does not.

degree of a vertex notation and formal definition

denoted delta(v) and is the number of edges connected to a vertex v