Group members: Sonja Boytcheva, Ben Foley, Edgar Velazquez

Given a graph G=(V,E) and two vertices s,t∈V, give the algorithm from class to determine a path from s to t in G if it exists.

Solution:

1. Initialize A={s}, S=∅.
2. Repeat the following until either t∈A or A=∅:

    a. Pick an x∈A, set S:=S∪{x}
   
    b. Let UnseenChild(x):={y|(x,y)∈E ∧ y∉S}
   
    c. Set A:=(A ∪ UnseenChild(x))−{x}

3. If A=∅ then output "there is no path s to t"
4. Otherwise, we can find a path in reverse order by looking in S for some x such that (x,t) ∈ E, then looking in S for some y such that (y,x) ∈ E, and so on until we get back to s. This will be a simple path.

Group members: Phuc Phan, Rayyan Khan, Prajesh Shrestha

check reflexive: (a,b) ~ (a,b) because a.b = c.d

check symmetric: if (a,b) ~ (c,d) which means a.b = c.d -> c.d = a.b -> (c,d)~(a,b)

check transitive: if(a,b) (c,d) and (c,d)(e,f) which means a.b = c.d and c.d = e.f -> a.b = e.f -> (a,b)~(e,f)

Conclude: ~ is an equivalence relation