Let G = (V, E) be a directed graph where V = {1, 2, , n}. Given a vertex v let Sv denote the set of vertices that have a path from v (excluding v), and let Tv be the set of vertices from which there is a path to v (excluding v). A vertex v is (1/3, 2/3) critical, if the size of Sv is (n 1)/3 and the size of Tv is 2(n 1)/3 and Sv and Tv are disjoint. Given a graph (where n 1 is divisible by 3), give an algorithm that outputs a (1/3, 2/3) critical, if one exists. Prove the correctness and derive the runtime. Part of the grade depends on efficiency

1. Let G- (V, E) be a directed graph where V-(1,2,.. ,n). Given a vertex v let Sv denote the set of vertices that have a path from v (excluding v), and let T, be the set of vertices from which there is a path to v (excluding v). A vertex v is (1/3, 2/3) critical, if the size of S, is (n -1)/3 and the size of T, is 2(n - 1)/3 and S and T, are disjoint. Given a graph (where n - 1 is divisible by 3), give an algorithm that outputs a (1/3, 2/3) critical, if one exists. Prove the correctness and derive the runtime. Part of the grade depends on efficiency, 1. Let G- (V, E) be a directed graph where V-(1,2,.. ,n). Given a vertex v let Sv denote the set of vertices that have a path from v (excluding v), and let T, be the set of vertices from which there is a path to v (excluding v). A vertex v is (1/3, 2/3) critical, if the size of S, is (n -1)/3 and the size of T, is 2(n - 1)/3 and S and T, are disjoint. Given a graph (where n - 1 is divisible by 3), give an algorithm that outputs a (1/3, 2/3) critical, if one exists. Prove the correctness and derive the runtime. Part of the grade depends on efficiency