Kombinatorikus módszerek gráfok és rúdszerkezetek merevségének vizsgálatában  részletek

súgó  nyomtatás 
vissza »
 

Projekt adatai

  
azonosító
49671
típus K
Vezető kutató Jordán Tibor
magyar cím Kombinatorikus módszerek gráfok és rúdszerkezetek merevségének vizsgálatában
Angol cím Combinatorial methods in the study of rigidity of graphs and frameworks
zsűri Matematika–Számítástudomány
Kutatóhely Operációkutatási Tanszék (Eötvös Loránd Tudományegyetem)
projekt kezdete 2005-01-01
projekt vége 2008-12-31
aktuális összeg (MFt) 2.195
FTE (kutatóév egyenérték) 0.60
állapot lezárult projekt





 

Zárójelentés

  
kutatási eredmények (magyarul)
A szerkezetek merevségi tulajdonságaira vonatkozó matematikai eredmények a statikai alkalmazásokon kívül számos más területen is hasznosíthatók. A közelmúltban sikerrel alkalmazták ezeket molekulák szerkezetének vizsgálataiban, szenzorhálózatok lokalizációs problémáiban, CAD feladatokban, stb. A kutatás célja gráfok és szerkezetek merevségi tulajdonságainak vizsgálata volt kombinatorikus módszerekkel. Igazoltuk az ú.n. Molekuláris Sejtés kétdimenziós változatát és jelentős előrelépéseket tettünk a molekuláris gráfok háromdimenziós merevségének jellemzésében is. A globálisan merev, avagy egyértelműen realizált gráfok elméletét kiterjesztettük vegyes - hossz és irány feltételeket is tartalmazó - vegyes gráfokra valamint az egyértelműen lokalizálható részekre is. Továbbfejlesztettük a szükséges gráf- és matroidelméleti módszereket. Új eredményeket értünk el a tensegrity szerkezetek, test-zsanér szerkezetek, valamint a merevség egy irányított változatával kapcsolatban is.
kutatási eredmények (angolul)
The mathematical theory of rigid frameworks has potential applications in various areas. It has been successfully applied - in addition to statics - in the study of flexibility of molecules, in the localization problem of sensor networks, in CAD problems, and elsewhere. In this research project we investigated the rigidity properties of graphs and frameworks by using combinatorial methods. We proved the two-dimensional version of the so-called Molecular Conjecture and made substantial progress towards a complete characterization of the rigid molecular graphs in three dimensions. We generalized the theory of globally rigid (that is, uniquely localized) graphs to mixed graphs, in which lengths as well as direction constraints are given, and to globally rigid clusters, or subgraphs. We developed new graph and matroid theoretical methods. We also obtained new results on tensegrity frameworks, body and hinge frameworks, and on a directed version of rigidity.
a zárójelentés teljes szövege http://real.mtak.hu/2015/
döntés eredménye
igen





 

Közleményjegyzék

  
Z. Fekete, T. Jordan: Rigid realizations of graphs on small grids, Computational Geometry, Vol. 32, Issue 3, pp. 216-222., 2005
B. Jackson, T. Jordan, Z. Szabadka: Globally linked pairs of vertices in equivalent realizations of graphs, Discrete and Computational Geometry, Vol. 35, 493-512,, 2006
B. Jackson, T. Jordan: On the rank function of the 3-dimensional rigidity matroid, Int. J. Comput. Geom. Appl., Vol. 16, No. 5-6, 415-429,, 2006
Z. Fekete, T. Jordan: Uniquely localizable networks with few anchors, Proc. 4th Japanese-Hungarian Symposium on Discrete Mathematics and Its Applications, Budapest, June 2005, 2005
T. Jordan, Z. Szabadka: Operations preserving global rigidity of graphs and frameworks in the plane, Computational Geometry, in press,, 2009
B. Jackson, T. Jordan: Rigid components in molecular graphs, Algorithmica, Vol. 48, No. 4, 399-412,, 2007
B. Jackson, T. Jordan: Rank and independence in the rigidity matroid of molecular graphs, EGRES TR-2006-02, 2006
B. Jackson, T. Jordan: Brick partitions of graphs, Discrete Mathematics, in press,, 2009
B. Jackson, T. Jordan: The generic rank of body-bar-and-hinge frameworks, European J. Combinatorics, to appear,, 2009
J. Bang-Jensen, T. Jordan: On persistent directed graphs, Networks, Vol. 52, Issue 4, 271-276,, 2008
T. Jordan, A. Recski, Z. Szabadka: Rigid tensegrity labelings of graphs, European J. Combinatorics, in press,, 2009
B. Jackson, T. Jordan: On the rigidity of molecular graphs, Combinatorica 28 (6), 645-658,, 2008
B. Jackson, T. Jordan: Pin-collinear body-and-pin frameworks and the molecular conjecture, Discrete and Computational Geometry 40: 258-278,, 2008
B. Jackson, T. Jordan: A sufficient connectivity condition for generic rigidity in the plane, Discrete Applied Mathematics, in press,, 2009
B. Jackson, T. Jordan: Graph theoretic methods in the analysis of uniquely localizable sensor networks, Localization algorithms and strategies for wireless sensor networks (G. Mao, B. Fidan, eds), IGI Global, in press,, 2009
S. Iwata, T. Jordan: Orientations and detachments of graphs with prescribed degrees and connectivity, Proc. 5th Hungarian-Japanese Symposium on Discrete Mathematics and Its Applications, Sendai, April 2007, 149-153,, 2007
B. Jackson, T. Jordan: Globally rigid circuits of the direction-length rigidity matroid, J. Combinatorial Theory, Ser. B, to appear,, 2009



vissza »