CSCE Quiz 3 - Graphs

graph

collection of vertices, edges, and functions.

undirected graph

AB = BA

connected graph

at least one path between every pair of vertices

complete graph

an edge connects every pair of vertices; every vertex is connected

trail

a walk with no repeated edges

path

a walk with no repeated edges or vertices

graphs are isomorphic when:

• same # of vertices

• same # of edges

• # same degree sequence

cyclic graph

has atleast ONE cycle

cycle

path that begins and ends at the same vertex

• no repeated edges or vertices

directed acyclic graph (DAG)

directed graph without a cycle

circuit

closed walk ; starts and ends at the same vertex

• can repeat vertices

• CANNOT repeat edges

euler trail

contains every edge exactly ONCE

• can only contain 2 odd deg vertices at beg or end

euler circuit

every edge appears exactly ONCE

hamilton path

valid walk that contains every vertex exactly ONCE

planar graph

no edge crossings

chromatic number

min # of colors needed in a graph

greedy algorithm

• doesn’t guarantee the min # of colors

• guarantees an upper bound on the number of colors

• BA never uses more than d+1 colors where d is the max degree of a vertex in the given graph

adj matrix

0 & 1 corresponding to relationship

adj list

list in ascending order

weighted graoh

0 → 1|10 → 2|20 → 3|7

graph traversal

visiting every edge exactly once in a well-defined order

breadth first search BFS

start traversing from a selected node (source) and explore all nodes at the present depth prior to moving on to the nodes at the next depth level.

depth first search DFS

start traversing from a selected node (source) and explore as far as possible along each branch before backtracking.

in DFS, vertices from which exploring is incomplete are processed in what type of order?

LAST IN FIRST OUT (STACK)

in BFS, vertices are explored and organized in what type of order?

FIRST IN FIRST OUT (QUEUE)

DFS contains two processing opportunities for each vertex v, when it

is “discovered” and when it is “finished”

TRUE

BFS contains only one processing opportunity for each vertex v, and

then it is dequeued.

TRUE

tree

a graph that is connected but has no cycles

• only one unique path between any two vertices

spanning tree

subgraph that includes all the vertices of G and connects

them using the minimum possible number of edges.

a spanning tree is connected and contains no cycles.

TRUE

properties of spanning trees

• does not exist for a disconnected graph.

• For a connected graph with N vertices the number of edges in a spanning tree for that graph will be N-1.

• does not have any cycle.

• We can construct a spanning tree for a connected graph by removing E-N+1 edges

cayleys theorem

nUMBER OF SPANNING TREES POSSIBLE : N = VERTICES

states that the number of spanning trees in a complete

graph with N vertices is N^(N-2)

adjacent

vertex a is adjacent to vertex b if there is an edge connecting the two

hamilton cycle

cycle that contains every vertex

real world situations for topological sorting

• event scheduling

• program dependencies

• assembly instructions

minimum spanning tree

spanning tree with skinniest waist

real world uses for min spanning tree

• network design

• clustering of data