《advanced+topics+in+graph+algorithms》由会员分享，可在线阅读，更多相关《advanced+topics+in+graph+algorithms（51页珍藏版）》请在金锄头文库上搜索。
1、Advanced Topics Graph AlgorithmsAdvanced Topics in Graph AlgorithmsFedor V. Fomin Paderborn 2002Advanced Topics Graph AlgorithmsLecture 1What is this course about?Advanced Topics Graph AlgorithmsWhat this course is about?GraphsAdvanced Topics Graph AlgorithmsWhat this course is about?Graphs?Problems
2、 on graphsAdvanced Topics Graph AlgorithmsWhat this course is about?Graphs?Problems on graphs?Algorithms to solve these problemsAdvanced Topics Graph AlgorithmsGraphsAdvanced Topics Graph AlgorithmsGraphsAdvanced Topics Graph AlgorithmsProblems?Graph coloring Advanced Topics Graph AlgorithmsMaximum
3、clique sizeAdvanced Topics Graph AlgorithmsIndependent setAdvanced Topics Graph AlgorithmsWhat properties of a graph can be useful to solve the problem?Advanced Topics Graph AlgorithmsBasics. Graph TheoryAdvanced Topics Graph AlgorithmsPath PCycle CIf is a path, the graph obtained from P by addingis
4、 cycleAdvanced Topics Graph AlgorithmsAdvanced Topics Graph AlgorithmsSome special graphs?Complete graph Kn?Trees?Bipartite graph?Complete bipartite graphAdvanced Topics Graph AlgorithmsCliqueAdvanced Topics Graph AlgorithmsAlgorithms?We say that an algorithm for problem runs in time O(f(n) if for s
5、ome constant c there exists an implementation of A which terminates after at most O(f(n) computational steps for all instances of size n.Advanced Topics Graph AlgorithmsLinear time algorithmAdvanced Topics Graph AlgorithmsHow to represent a graph?Adjacency list?Adjacency matrixAdvanced Topics Graph
6、AlgorithmsExample of linear problem:converting the adjacency list of a graph into sorted adjacency lists.Advanced Topics Graph AlgorithmsAdvanced Topics Graph AlgorithmsBuck sortingAdvanced Topics Graph AlgorithmsBuck sortingAdvanced Topics Graph AlgorithmsBuck sorting?Buck sorting takes O(n+di) tim
7、eAdvanced Topics Graph AlgorithmsAlgorithmAdvanced Topics Graph AlgorithmsTheorem?Algorithm Sorting the Adjacency Lists of Sorting the Adjacency Lists of GraphsGraphs runs in O(m+n)time. Advanced Topics Graph AlgorithmsProof:Advanced Topics Graph AlgorithmsAnother examples?Testing planarity, connect
8、ivity, biconnectivityAdvanced Topics Graph AlgorithmsNP complete problemsAdvanced Topics Graph AlgorithmsPart 1. Perfect graphsAdvanced Topics Graph AlgorithmsClique and ISAdvanced Topics Graph AlgorithmsColouringAdvanced Topics Graph AlgorithmsDefinition of perfect graphsAdvanced Topics Graph Algor
9、ithmsExamples of perfect graphs?Bipartite graphs?Cliques?Odd cycle - NOT?More examples to appear laterAdvanced Topics Graph AlgorithmsExample: Integer programmingDefineandAdvanced Topics Graph AlgorithmsExample: Integer programming# of IS containigisAdvanced Topics Graph AlgorithmsExampleAdvanced To
10、pics Graph AlgorithmsExampleThe dualAdvanced Topics Graph AlgorithmsExampleAdvanced Topics Graph AlgorithmsExampleIf graph is perfect Advanced Topics Graph AlgorithmsExample: Final remarkFor linear programming (solution is not necessarily integer) the value of an optimal solution of the primal is eq
11、ual to the value of an optimal solution of the dual. Stating graph problems as linear programming problem leads to an interesting field: fractional graph theory. In fractional graph theory it is possible that the fractional chromatic number is not integer but it should be equal to fractional clique
12、number!Advanced Topics Graph AlgorithmsChapter I. CHORDAL GRAPHSCHORDAL GRAPHS PLAY VERY IMPORTANT ROLE IN OUR COURSE.Advanced Topics Graph AlgorithmsDefinition of chordal graph?A chord of a cycle Cis an edge not in Cthat has endpoints in C?A chordless cycle in Gis a cycle of length more than three
13、that has no chord.?A graph Gis chordal if it does not contain a chordless cycle. Advanced Topics Graph AlgorithmsSimlicial vertex: definitionAdvanced Topics Graph AlgorithmsHereditary property?Exercise: Prove that chordality is hereditary property. (In other words, every induced subgraph of a chorda
14、l graph is chordal.)Advanced Topics Graph AlgorithmsWe shall prove that every chordal graph has a simplicial vertex. Since chordality is hereditary property, this implies the following naive algorithm of testing chordality of a graph G: o While there are simplicial vertices do o Find a simplicial ve
15、rtex and remove it o If the resulting graph is empty thenGis chordal o Else G is not chordalAdvanced Topics Graph AlgorithmsRunning time of the naive algorithmAdvanced Topics Graph AlgorithmsPE-ordering definitionVertex ordering of a graph G=(V,E) is a PE-ordering(perfect elimination ordering) if fo
16、r everyvertex viis simplicial in the graph induced by vertex set Advanced Topics Graph AlgorithmsMinimal separators?A subset S of vertices of a connected graph G is called an a,b- separator for non adjacent vertices a and b in V(G) S if a and b are in different connected component of the subgraph of G induced by V(G) S.?If no proper subset of an a,b-separator S separates a and b in this way, then S is called aminimal a
