On One Class of Undirected Graph
Control Science and Engineering
Volume 1, Issue 1, December 2017, Pages: 1-3
Received: Apr. 1, 2017; Accepted: Apr. 18, 2017; Published: May 31, 2017
Views 3246      Downloads 124
Authors
Kochkarev Bagram, Department of Mathematics and Mathematical Modelling, Institute of Mathematics and Mechanics Named After N. I. Lobachevsky, Kazan (Volga Region) Federal University, Kazan, Russia
Sibgatullovich, Department of Mathematics and Mathematical Modelling, Institute of Mathematics and Mechanics Named After N. I. Lobachevsky, Kazan (Volga Region) Federal University, Kazan, Russia
Article Tools
Follow on us
Abstract
Introduced the concept of polynomial combinatorial sets in enumerative combinatorics and formulates the problem of finding some element with an easily recognized symptom among elements of a combinatorial set. We build an efficient algorithm to solve this problem. We prove that this algorithm does not fit into the formal definition of an algorithm (e.g. “Turing machine”). It is proved that all NP-complete problems are not polynomial. We consider a countable class of undirected Hamiltonian graphs with an odd number of vertices without loops and multiple edges. We prove one typical feature of such graphs: almost every simple path containing all the vertices of the graph is not Hamiltonian cycle. In other words, in the langage of probability theory, the probability that a randomly selected a simple path in this graph containing all vertices, is Hamiltonian cycle tends to zero with growth of number vertices.
Keywords
An Undirected Graph, A Simple Path, Hamiltonian Cycle, Polynomial Combinatorial Set, Non-polynomial Combinatorial Set
To cite this article
Kochkarev Bagram, Sibgatullovich, On One Class of Undirected Graph, Control Science and Engineering. Vol. 1, No. 1, 2017, pp. 1-3. doi: 10.11648/j.cse.20170101.11
Copyright
Copyright © 2017 Authors retain the copyright of this article.
This article is an open access article distributed under the Creative Commons Attribution License (http://creativecommons.org/licenses/by/4.0/) which permits unrestricted use, distribution, and reproduction in any medium, provided the original work is properly cited.
References
[1]
Kochkarev B. S. Gipoteza J. Edmondsa I problema S. A. Kuka //Vestnik TGGPU, 2011 2 (24) s. 23-24 (in Russian).
[2]
Kochkarev B. S. On Cook’s problem. http://www.math.nsc.ru/conference/.
[3]
Kochkarev B. S. Prilogenie monotonnykh funktsii algebry logiki k probleme Kuka, Nauka v Vuzakh: matematika, fizika, informatika. Tezisy dokladov Mejdunarodnoj nauchno-obrazovatelnoj konferentsii, 2009, pp274-275 (in Russian).
[4]
Kochkarev B. S. About one class polynomial problems with not polynomial certificates //arXiv: 1210. 7591v1 [math. CO] 29 Oct. 2012.
[5]
Kochkarev B. S. Proof of the hypothesis Edmonds’s, not polynomial of NPC problems and classification of the problems with polynomial certificates. //arXiv: 1303. 2580v1 [cs. CC] Mar 2013.
[6]
Kochkarev B. S. Typical property of one class of combinatory objects and estimatin from above corresponding combinatory numbers //arXiv: 1304. 4363v1 [cs. DM] 16Apr 2013.
[7]
Kochkarev B. S. About one class polynomial problems with not polynomial certificates //Second International Conference “Claster Computing” CC 2013 (Ukraine, Lviv, June 3-5, 2013) P. 99-100.
[8]
Kochkarev B. S. Dokazatelstvo gipotezy Edmondsa I reshenie problem Kuka. Nauka, Tekhnika I Obrazovanie, 2014, 2 (2) s. 6-9 (in Russian).
[9]
Kochkarev B. S. Vzaimootnosheniya mejdu slojnostnymi klassami P, NPi NPC Problems of modern science and education. 2015, 11(41). S. 6-8 (in Russian).
[10]
Kochkarev B. S. Problem of Recognition of Hamiltonian Graph //International Journal of Wirless Communication and Mobile Computing 2016; 4 (2): 52-55.
[11]
Kochkarev B. S. Typical Properties of Maximal Sperner Families of Type (k, k+1) and Upper Esnimate. //IOSR Journal of Mathematics (IOSR-JM) Volum 13, Issue 2 Ver II (Mar-Apr. 2017) PP. 16-23.
[12]
Wiles A. Modular elliptic curves and Fermat’s Last Theorem Annals of Mathematics. V. 141 Second series 3 May 1995 pp. 445-551.
[13]
Kochkarev B. S. Ob odnom klasse algebraicheskikh uravnenij, ne imejutshikh ratsionalnykh reshenij //Problem of moden science and education. 2014. 4(22) s. 9-11.
[14]
Kochkarev B. S. Algorithm of search of Large Prime Numbers //International Journal of Discrete Mathematics, 2016; 1 (1): 30-32.
[15]
Kochkarev B. S. About One Binary Problem in a class of algebraic equations and Her Communication with The Great Hypothesis of Fermat //International Journal of Current Multidisciplinary Studies Vol. 2, Issue, 10, pp. 457-459, October, 2016.
[16]
Stanley R. P. Enumerative Combinatorics v. 1, 1986.
[17]
Yablonsky S. V. Vvedenie v diskretnuyu matematiku Moskow, 1986, P. 384.
[18]
Cormen T. H., Ch. E. Leiserson, Rivest R. L. Algoritmy, postroenie I analiz, 2002, MTSNMO, Moskow P. 960.
[19]
Ravenstvo klassov P i NP https://ru.wikipedia.org/wiki
[20]
Karp R. M. Reducibility among combinatorial problems. //In Raymond E, Miller and James W. Thatcher, editors, Complexity of computer Computations, P. 85-103, Plenum Press, 1972.
ADDRESS
Science Publishing Group
1 Rockefeller Plaza,
10th and 11th Floors,
New York, NY 10020
U.S.A.
Tel: (001)347-983-5186