assignment 4

Assignment 4 due by the end of class Wednesday February 7 2001.

Starting from vertex A, trace both versions of the lexbfs algorithm on the graph below. (i) In the first version, show the lexicographic label of each vertex at each step of the algorithm, and show the final lexbfs tree. (ii) In the second version, show the queue of sets at each step of the algorithm.
```
a: d g i
b: e g h
c: e f g i
d: a g j
e: b c g i
f: c g i
g: a b c d e f h i j
h: b g j
i: a c e f g
j: d g h
```
Using the lexbfs order from the previous question, trace the algorithm which checks whether a vertex ordering is simplicial. Show each repetition set A[x] at each step of the algorithm.
Describe in detail how you would implement the queue-of-sets version of lexbfs so that it runs in linear time. Describe all data structures, and give a careful and complete analysis of the running time.
Consider a lexbfs ordering (v_1, v_2, ..., v_n) of a graph. Prove that v_n is simplicial if the graph is chordal. Hint: Assume that v_n is not simplicial. Then it has neighbours v_j,v_k with j less than k which are not adjacent. Now v_n, which was ordered after v_k, is adjacent to v_j, but v_k is not adjacent to v_j. But v_k was ordered before v_n ... so what can we conclude about v_k's neighbourhood? Once you have answered this question, continue the argument until you have constructed a chordless cycle with at least four vertices.
Describe in detail how to modify simplicial order checking algorithm so that it returns an induced cycle (with four or more vertices) whenever the graph is not chordal.