Path Partition in Directed Graph – Modeling and Optimization

Abstract

The concept of graph theory is therefore perfectly suitable to structure a problem in its initial analysis phases since a graph is the most general mathematical object. At the structural level, the nodes represent the objects, the variables… and the arc forms the binary relation of influence among them. Many real problems can be modeled as path partition in directed graph that played particular role in the operation of arranging a set of nodes especially in case of directed acyclic graph (DAG). We encounter such graph in schedule problems, the analysis of language structure, the probability theory, the game theory, compilers…. Moreover managerial problem can be modeled as acyclic graphs, also the potential problem has a suitable solution if and only if the graph is acyclic

Keywords

• Acyclic graph,Path Partition,tournament,Hamiltonian circuit,Adjacency list,Adjacency matrix,canonical ordering,Spanning tree

Path Partition in Directed Graph-Modeling and Optimization

Öz

References

1. Abdel Kader I., Decomposition of directed graph, International conference on applied analysis and algebra (ICAAA), 29 June – 2 July, Istanbul 2011, Editor Irfan Siap, Adam Kilicman, Mustafa Bayram.
2. Abdel Kader I, Directed Acyclic graph and e-Management, flight program assignment, the third international arab conference on e- Technology, proceeding of IACe-T, Zarqa Univeristy, Jordan, 25-27 April 2012, Editors: Fawarah H. And Al-Qerem A.
3. Aho A.V., Hopcroft J.E. and Ullman J.D., the design and analysis of computer algorithms, Addison-wesley, Reading M A, 1974.
4. Alspach Brian R., Pullman Norman J., "Path decomposition of digraphs", Bull. Austral. Math. Soc., 10(1974), 421-427.
5. Bang-Jensen J., Gutin G., "Generalization of Tournaments, a survey, J.Graph Theory 28, 171-202, 1998.
6. Bang-Teusen J., Gutin G., “Digraphs: Theory, Algorithms and Application”, 2nd edition Springer, 2008.
7. Beineke L.W. Wilson R.J., "A survey of recent results on the tournaments", 31-48, in Recent Advances in Graph Theory, Proc. Prague, 1974, Academia.
8. Berge C., "Graphes et Hypergraphes", Dunod Paris 1970.

9. Bondy J. A., Murty V.S.R., Graph Theory, Springer, 2008.
10. Camion P., "Quelques proprites de chemins et dans circuits Hamiltonienes dus la Theorie des graphes", Cahiers de Centre d'Etude de recherche opeiatiannelles 2, 10-15, 1960.
11. Chaty G., Chein M., "path-number of k-graphs and symmetric digraphs", proceeding of seventh southeastern conference on combinatorics, Graph Theory and Computing, 203-216, (Louisana state University, Baton-Roage, 1976, Congressus Numerantium, 17, utilities Mathematics Winnipeg, 1976.
12. Distel R., Graph Theory, Springer, Third Edition, 2008.
13. Douglas R.J., “Tournament that admit exactly one Hamiltonian circuit”, Proc. London Math. Soc. N0 4, 716-730, 1970.
14. Galperin H., and wigderson A., succinct representation of graphs, Inform and control 56(1983) pp183-198.
15. Garey M.R. M., "On enumerating tournaments that admit exactly one Hamiltonian circuit", J. Comb. Theory B, 13, 266-269, 1972.
16. Gutin, G. Rafieg, Yev, A. On n-partite tournament with unique n-cycle. To appear in Graph and Combination. Harary F., Moser L., « The theory of round robin tournaments” Amer. Math. Month 73, 231-246, 1966.
17. Itai A. and Rodeh M., Representation of Graphs, Acta Inform. 17 (1982) 215-219.
18. Las-Vergnas M., "Sur le nombre de circuits dans un tournoi fortement connexe ", Cahiers du centre d'Etude de Recherche opérationnelle Belge, Vol. 17, 261-265. Manoussakis Y., "A linear-Time Algorithm for Finding Hamiltonian cycle in Tournaments", Discrete Appl. Math. 36, 199-201, 1992.
19. Moon J. W., "Topics on Tournaments", Holts Reinehart and Winston, 1968.
20. O' Brien R.C., "An upper bound on the path number of a digraph", J. combinatorial theory seri B22 (1977), 168-174.
21. Ore Oystein, "Theory of graphs", American Mathematical Society colloquium publications, 38, American Mathematical society, providence, Rhode Island, 1962.
22. Reid K. B., Tournaments, Handbook of Graph Theory, C.R. C Press L.L.C., 2004.
23. Reid K.B., "Tournaments scores, Kings, Generalizations and Special Topics", Congresses number 115, 171-211, 1996.
24. Reid K.B., Beinke L.W., "Tournaments in select Topics in graph Theory, 169-204, Academia Press, London, 1979.