جلسه دوم: مسایل ان‌پی

مروری بر الگوریتم کارشناسی! (چون بقیه‌اش خیلی آسون بود!)

2-SAT

Construct the implication graph of the instance, and find its strongly connected components using any of the known linear-time algorithms for strong connectivity analysis.

Check whether any strongly connected component contains both a variable and its negation. If so, report that the instance is not satisfiable and halt.

Construct the condensation of the implication graph, a smaller graph that has one vertex for each strongly connected component, and an edge from component i to component j whenever the implication graph contains an edge uv such that u belongs to component i and v belongs to component j. The condensation is automatically a directed acyclic graph and, like the implication graph from which it was formed, it is skew-symmetric.

Topologically order the vertices of the condensation. In practice this may be efficiently achieved as a side effect of the previous step, as components are generated by Kosaraju's algorithm in topological order and by Tarjan's algorithm in reverse topological order.[7]

For each component in this order, if its variables do not already have truth assignments, set all the terms in the component to be false. This also causes all of the terms in the complementary component to be set to true.

http://en.wikipedia.org/wiki/2-satisfiability

دور اویلری:

Fleury's algorithm is a straightforward algorithm for finding Eulerian paths/tours. It proceeds by repeatedly removing edges from the graph in such way, that the graph remains Eulerian. A version of the algorithm, which finds Euler tour in undirected graphs follows.

Start with any vertex of non-zero degree. Choose any edge leaving this vertex, which is not a bridge (i.e. its removal will not disconnect the graph into two or more disjoint connected components). If there is no such edge, stop. Otherwise, append the edge to the Euler tour, remove it from the graph, and repeat the process starting with the other endpoint of this edge.

Though the algorithm is quite simple, it is not often used, because it needs to identify bridges in the graph (which is not a trivial thing to code.) Slightly more sophisticated, but easily implementable algorithm is presented below.

***

Cycle finding algorithm

This algorithm is based on the following observation: if C is any cycle in a Eulerian graph, then after removing the edges of C, the remaining connected components will also be Eulerian graphs.

The algorithm consists of finding a cycle in the graph, removing its edges and repeating these steps with each remaining connected component. It has a very compact code with recursion:

'tour' is a stack

find_tour(u):

for each edge e=(u,v) in E:

remove e from E

find_tour(v)

prepend u to tour

to find the tour, clear stack 'tour' and call find_tour(u),

where u is any vertex with a non-zero degree.

**

Algorithm for undirected graphs:

1)Start with an empty stack and an empty circuit (eulerian path).

- If all vertices have even degree - choose any of them.

- If there are exactly 2 vertices having an odd degree - choose one of them.

- Otherwise no euler circuit or path exists.

2)If current vertex has no neighbors - add it to circuit, remove the last vertex from the stack and set it as the current one. Otherwise (in case it has neighbors) - add the vertex to the stack, take any of its neighbors, remove the edge between selected neighbor and that vertex, and set that neighbor as the current vertex.

3)Repeat step 2 until the current vertex has no more neighbors and the stack is empty.

Note that obtained circuit will be in reverse order - from end vertex to start vertex.

http://en.wikipedia.org/wiki/Eulerian_path

http://www.algorithmist.com/index.php/Euler_tour

http://www.graph-magics.com/articles/euler.php

مولفه‌های قویاً همبند گراف:

http://en.wikipedia.org/wiki/Strongly_connected_component#Algorithms

http://en.wikipedia.org/wiki/Kosaraju%27s_algorithm

http://en.wikipedia.org/wiki/Tarjan%27s_strongly_connected_components_algorithm

http://en.wikipedia.org/wiki/Path-based_strong_component_algorithm

اولی رو من سر کلاس گفتم، دومی رو استاد سر کلاس گفتند و سومی رو هم بلد نیستم! :))

tractability:

Tractable Problem: a problem that is solvable by a polynomial-time algorithm. The upper bound is polynomial.

Intractable Problem: a problem that cannot be solved by a polynomial-time algorithm. The lower bound is exponential.

البته سه نوع مسأله به وجود می‌آید:

– Problems with known polynomial-time algorithms.

– Problems that are provably intractable (proven to have no polynomial-time

algorithm).

– Problems with no known polynomial-time algorithm but not yet proven to be

intractable.

در ضمن نمی‌شود با اثبات اینکه خروجی نمایی است ثابت کرد که الگوریتم هم نمایی است.

http://www.cs.ucc.ie/~dgb/courses/toc/handout29.pdf