9SfqSqum

1\documentclass[12pt]{article}%
2\usepackage{amsfonts}
3\usepackage{fancyhdr}
4\usepackage{comment}
5\usepackage[a4paper, top=2.5cm, bottom=2.5cm, left=2.2cm, right=2.2cm]%
6{geometry}
7\usepackage{times}
8\usepackage{amsmath}
9\usepackage{changepage}
10\usepackage{amssymb}
11\usepackage{graphicx}%
12\setcounter{MaxMatrixCols}{30}
13\newtheorem{theorem}{Theorem}
14\newtheorem{acknowledgement}[theorem]{Acknowledgement}
15\newtheorem{algorithm}[theorem]{Algorithm}
16\newtheorem{axiom}{Axiom}
17\newtheorem{case}[theorem]{Case}
18\newtheorem{claim}[theorem]{Claim}
19\newtheorem{conclusion}[theorem]{Conclusion}
20\newtheorem{condition}[theorem]{Condition}
21\newtheorem{conjecture}[theorem]{Conjecture}
22\newtheorem{corollary}[theorem]{Corollary}
23\newtheorem{criterion}[theorem]{Criterion}
24\newtheorem{definition}[theorem]{Definition}
25\newtheorem{example}[theorem]{Example}
26\newtheorem{exercise}[theorem]{Exercise}
27\newtheorem{lemma}[theorem]{Lemma}
28\newtheorem{notation}[theorem]{Notation}
29\newtheorem{problem}[theorem]{Problem}
30\newtheorem{proposition}[theorem]{Proposition}
31\newtheorem{remark}[theorem]{Remark}
32\newtheorem{solution}[theorem]{Solution}
33\newtheorem{summary}[theorem]{Summary}
34\newenvironment{proof}[1][Proof]{\textbf{#1.} }{\ \rule{0.5em}{0.5em}}
35
36\newcommand{\Q}{\mathbb{Q}}
37\newcommand{\R}{\mathbb{R}}
38\newcommand{\C}{\mathbb{C}}
39\newcommand{\Z}{\mathbb{Z}}
40
41\begin{document}
42
43\title{Theoretical Assignment 4}
44\author{HARSH THAKUR(160279)}
45\date{\today}
46\maketitle
47\section{Problem 1}
48\subsection{}
49There can not exist cross edges and forward edges in the DFS tree of a unique path directed graph. It is explained with the help of a figure:\newline
50Because of a forward edge there are two paths between 3 and 12:3$\Rightarrow$12 and 3$\Rightarrow$7$\Rightarrow$12.\newline
51Because of a cross-edge there are two paths between 1 and 10:1$\Rightarrow$2$\Rightarrow$5$\Rightarrow$10 and 1$\Rightarrow$3$\Rightarrow$7$\Rightarrow$11$\Rightarrow$10.
52Usually back-edges don't matter but there are special cases, like in the picture you can see there are two paths from 8 to 2:8$\Rightarrow$2 and 8$\Rightarrow$13$\Rightarrow$1$\Rightarrow$2. 
53\subsection{Theorem}
54The graph G is not a unique path graph if and only if in its DFS tree:\newline
55(a) There are forward edges.\newline
56(b)There are cross edges.\newline
57(c)There exists vertex a v,such that the sub-tree rooted at v has 2 or more than 2 back edges to ancestors of v.\newline
58\begin{proof}
59Consider there is a cross edge from a to b.Now the root has unique paths to a and b using the tree edges, but there exists yet another path to b: root to a using tree edges then to b using the cross edge.\newline
60Consider there is a forward edge from a to b,now we can go from a to b using the tree edges(as b is a descendent of a) or using the forward edge.\newline
61Consider that the subtree rooted at v has two back-edges to the ancestors of v.Let the ancestors be a1 and a2 where a1 is the lower ancestor in the dfs tree. Now we can go to a1 using one of the back-edge or by going to a2 then descend to a1 using tree edges.\newline
62In all of the three cases there exists 2 paths between a pair of vertices therefore they are not unique path graphs.\newline
63\newline
64For the second part of the proof, let's assume that the graph G's DSF traversal does not give us any forward or cross edges, but G is not a unique path graph. Then there will exist two vertices x and y such that there are two paths from x to y: x$\Rightarrow$...... $\Rightarrow$a$\Rightarrow$y and x$\Rightarrow$.......$\Rightarrow$b$\Rightarrow$y.\newline
65There can be only one tree edge to y:\newline
66(a)a$\Rightarrow$y is a tree edge(b$\Rightarrow$y is a back edge).\newline
67Now consider the path from y to b, let z be the first vertex after y. Now x should lie on this path as it has to reach b without travelling through y.Now since the subtree rooted at z does not have 2 back edges and x lies in this subtree, there is no way for x to reach a. So this case is not possible.\newline
68(b)a$\Rightarrow$y and b$\Rightarrow$y are both back edges.\newline
69Now y should be the lowest common ancestor of a and b as if there is any lower vertex to satisfy this property then it would defy property 3 in our theorem statement. Then x should lie on the path from y to a and also on the path from y to b, that means x is a common ancestor of a and b(lower than y to justify the back edges), which is a contradiction. 
70\end{proof}
71\subsection{Algorithm}
72We create a graph G' from G which is a condensation of G, having nodes as the strongly connected components as in PA6Q1, which is achieved in linear time by applying DFS. There can't be multiple edges between nodes of G'. Let's say that the SCC1 has nodes a1 and a2 and SCC2 has nodes b1 and b2 and a1$\Rightarrow$b1,a2$\Rightarrow$b2. Then we can reach from a1 to b1 through a2 and b2.\newline
73The vertices of G are in either the same SCC or different SCC.\newline
74If they are in the same SCC then we can detect forward and cross edges in O(n) time. To check for back edges we can associate a property to each vertex or create an array of size m to update the number of back edges in the sub tree to proper ancestors, for any array element >=2 value the function exits returning false value.This is also done in linear time by DFS.\newline
75For the second case,in graph G' there will exist multiple paths between two nodes.We apply DFS from each vertex in G' and detect forward or cross edges. Obviously there are not any back edges. DFS will take O(m) time as there are at max m-1 edges. Total time for all vertices is therefore O($m^{2}$).
76
77\section{Problem 2}
78\subsection{Vertex Set and Edge Set}
79The graph is formed using all the variable terms present in the CNF expression,as well as their negations as nodes.\newline
80For Example:
81
82    E =(x1 \vee x3) \wedge (!x1 \vee x4) \wedge (x2 \vee x3) \wedge (x2 \vee x4).
83
84Then the nodes are x1,x2,x3,x4,!x1,!x2,!x3,!x4.\newline
85Now for the edge set.\newline
86a $\vee$ b $\equiv$ !a$\Rightarrow$ b $\equiv$ b$\vee$ a $\equiv$ !b $\Rightarrow$ a \newline
87Now for each or expression a$\vee$ b we will make a directed edge from !a to b and !b to a.
88Each directed edge x to y means x implies y.\newline
89\subsection{Satisfiability}
90If there exist paths x,a1,a2......!x and !x,b1,b2.....x then the graph is not satisfiable,i.e there is a cycle of which x and !x are parts of.
91Existence of these paths imply x$\Rightarrow$a1$\Rightarrow$a2......$\Rightarrow$!x $\equiv$ x$\Rightarrow$!x and similarly !x$\Rightarrow$x. Which is a contradiction,as x and !x can't have the same truth value.
92If x and !x are parts of the same strongly connected component then also the CNF is not satisfiable.
93\subsection{Assigning values}
94If the graph is satisfiable, we apply DFS at each node. And of the n*n truth table of x1...xn we keep eliminating rows by the following rules, and finally the rows which are left will satisfy the expression.
95\subsubsection{x$\Rightarrow$!x}
96If this path is found, then x must have value false.
97\subsubsection{!x$\Rightarrow$x}
98If this path is found, then x must have value true.
99\subsubsection{x$\Rightarrow$y}
100If this path is found, then x and y can not simultaneously take values true and false respectively.
101\subsubsection{x$\Rightarrow$!y}
102If this path is found, then x and y can not simultaneously be true.
103\subsubsection{x$\Rightarrow$y and x$\Rightarrow$!y}
104If both of these paths are found, then x must have value false.
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126    
127    
128
129
130       
131                       
132\end{document}