{"entities":{"Q686419":{"pageid":688268,"ns":120,"title":"Item:Q686419","lastrevid":63470823,"modified":"2026-04-11T13:23:13Z","type":"item","id":"Q686419","labels":{"en":{"language":"en","value":"Enumeration of acyclic walks in a graph"}},"descriptions":{"en":{"language":"en","value":"scientific article; zbMATH DE number 428261"}},"aliases":{},"claims":{"P31":[{"mainsnak":{"snaktype":"value","property":"P31","hash":"fd5912e4dab4b881a8eb0eb27e7893fef55176ad","datavalue":{"value":{"entity-type":"item","numeric-id":56887,"id":"Q56887"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q686419$994BCECD-A7E7-40A0-9FEC-BBE1542C389A","rank":"normal"}],"P159":[{"mainsnak":{"snaktype":"value","property":"P159","hash":"eaedc77e1d2ca6ffeb2330df529731c3763ff714","datavalue":{"value":{"text":"Enumeration of acyclic walks in a graph","language":"en"},"type":"monolingualtext"},"datatype":"monolingualtext"},"type":"statement","id":"Q686419$679674C0-2563-4214-BF30-4E5DEE1EC8B6","rank":"normal"}],"P225":[{"mainsnak":{"snaktype":"value","property":"P225","hash":"0b99f3a6ea7a1e3264cb211c95843eb4bf2d0a1a","datavalue":{"value":"0783.05056","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q686419$717AB76E-BF97-4055-9DDC-FB9ED55674EB","rank":"normal"}],"P27":[{"mainsnak":{"snaktype":"value","property":"P27","hash":"57db3da74066782613e81285124daeea717cfd69","datavalue":{"value":"10.1016/0166-218X(93)90055-S","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q686419$B078B84B-F77B-4E87-BA72-4E29AA4108C9","rank":"normal"}],"P16":[{"mainsnak":{"snaktype":"value","property":"P16","hash":"f31efbc2df32459de8048dc57e82b32c17d4d68c","datavalue":{"value":{"entity-type":"item","numeric-id":686417,"id":"Q686417"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q686419$4BBDDDCE-25A4-456F-A2DB-E86CDFE0E1A3","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P16","hash":"460e075e6f4236fe5804e07af6be8711243af4a2","datavalue":{"value":{"entity-type":"item","numeric-id":686418,"id":"Q686418"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q686419$0FD6F81F-DE23-4170-A84D-4CD068938AD0","rank":"normal"}],"P200":[{"mainsnak":{"snaktype":"value","property":"P200","hash":"087f55844cc920aae060b09644168bf17b022e1a","datavalue":{"value":{"entity-type":"item","numeric-id":96294,"id":"Q96294"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q686419$79A8F759-3D9C-4B8F-93D4-4829EAE705D3","rank":"normal"}],"P28":[{"mainsnak":{"snaktype":"value","property":"P28","hash":"3394657ae3089c2788ad0bc1b6f1e244cbee8664","datavalue":{"value":{"time":"+1993-12-07T00:00:00Z","timezone":0,"before":0,"after":0,"precision":11,"calendarmodel":"http://www.wikidata.org/entity/Q1985727"},"type":"time"},"datatype":"time"},"type":"statement","id":"Q686419$2B3D8CAC-77BE-45A6-9E56-66B6DB65103A","rank":"normal"}],"P1448":[{"mainsnak":{"snaktype":"value","property":"P1448","hash":"851fd3eb904714a90d5b64e981858b72608b85dd","datavalue":{"value":"Acyclic walk of a graph is a closed walk whose projection is a tree. Let \\(S\\) be a subtree of \\(G\\). Denote by \\(v_ 1,\\ldots,v_{t_ S}\\) those vertices of \\(G-S\\) which are adjacent with vertices of \\(S\\) in \\(G\\). Let \\(g_ i\\) denote the number of vertices of \\(S\\) adjacent with \\(v_ i\\), \\(1 \\leq i \\leq t_ S\\). Let \\(\\omega_ \\ell(G)\\) and \\(\\omega_ \\ell^{ac}(G)\\) denote the number of closed and acyclic walks of \\(G\\), respectively, with length \\(\\ell\\). It is shown that \\(\\omega_ \\ell^{ac}(G)=\\sum_ Sm(S)\\cdot \\omega_ \\ell(S)\\), where \\(S\\) goes over all subtrees of \\(G\\), and \\(m(S)=\\prod^{t_ S}_{i=1}(1-g_ i)\\).","type":"string"},"datatype":"string"},"type":"statement","id":"Q686419$A736B909-95AA-46C8-840C-CEA412FB0255","rank":"normal"}],"P1447":[{"mainsnak":{"snaktype":"value","property":"P1447","hash":"8146f5feb228c23e2fa6738cca425f9e847fc191","datavalue":{"value":{"entity-type":"item","numeric-id":335340,"id":"Q335340"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q686419$18085DB2-4B91-4691-89DF-B64DED019D3B","rank":"normal"}],"P226":[{"mainsnak":{"snaktype":"value","property":"P226","hash":"1de0493fc6f7fe4361a54e7c2f5546e4ec52adf0","datavalue":{"value":"05C30","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q686419$A0C55EB7-C800-4796-A625-A0F2750E960B","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P226","hash":"d5da87a72c21717089feda882f568938059a9d84","datavalue":{"value":"05C05","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q686419$7F2E0C8F-8E03-4BEB-83A9-DCB97151FF9C","rank":"normal"}],"P1451":[{"mainsnak":{"snaktype":"value","property":"P1451","hash":"e91c3e3e00c45f85e74ecbb1282135cc572a202f","datavalue":{"value":"428261","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q686419$8D42A173-8C3C-4B66-A25A-35FD1F8CC3CC","rank":"normal"}],"P1450":[{"mainsnak":{"snaktype":"value","property":"P1450","hash":"fe740fac1b6a94b2a6ac2018b643d07167f1e099","datavalue":{"value":"closed walk","type":"string"},"datatype":"string"},"type":"statement","id":"Q686419$28EB5902-BCF1-42F1-828F-224B0DFF2DC3","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"534805fa6153b1b3786edcd60407ef0861005e9a","datavalue":{"value":"tree","type":"string"},"datatype":"string"},"type":"statement","id":"Q686419$5427D5DC-568D-4ED4-9876-E012EA2D89C7","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"c7d723019c1c528e39fc64584e06afa6b8aeecb0","datavalue":{"value":"acyclic walks","type":"string"},"datatype":"string"},"type":"statement","id":"Q686419$2E76AF68-1C02-4337-8711-BAACE93FD3CD","rank":"normal"}],"P1460":[{"mainsnak":{"snaktype":"value","property":"P1460","hash":"57f7fea50d2ce1b39b695c4a1313582eed405e38","datavalue":{"value":{"entity-type":"item","numeric-id":5976449,"id":"Q5976449"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q686419$DE98BB83-2172-4594-B300-CC91929FC857","rank":"normal"}],"P223":[{"mainsnak":{"snaktype":"value","property":"P223","hash":"a25070aa6b2bfe19dc398e052b4e7395286998c4","datavalue":{"value":{"entity-type":"item","numeric-id":3795617,"id":"Q3795617"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q686419$7F9AC14C-A25F-4D17-B157-FE52C04E975A","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"9c53238d3d5db8f813b51207e063ca7a3d3466d9","datavalue":{"value":{"entity-type":"item","numeric-id":4552272,"id":"Q4552272"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q686419$F16CD585-A83B-45BA-A52A-17A8E5D215FC","rank":"normal"}],"P1643":[{"mainsnak":{"snaktype":"value","property":"P1643","hash":"d2f3fc46cc9713ccbd63e6f0f5259ae3db9d0ffc","datavalue":{"value":{"entity-type":"item","numeric-id":1431887,"id":"Q1431887"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"84d497d57ca3003e1abf7f1cf56331929eabc5c9","datavalue":{"value":{"amount":"+0.9091379","unit":"1"},"type":"quantity"},"datatype":"quantity"}],"P1660":[{"snaktype":"value","property":"P1660","hash":"ba354e87a58191d58d132c60481c945a3234ce85","datavalue":{"value":{"entity-type":"item","numeric-id":6534273,"id":"Q6534273"},"type":"wikibase-entityid"},"datatype":"wikibase-item"}]},"qualifiers-order":["P1659","P1660"],"id":"Q686419$AC03F88B-3B7A-49D4-9A90-8BAC10025B98","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"8c92279bc7336975432235a1824cc22c100fcccd","datavalue":{"value":{"entity-type":"item","numeric-id":3077212,"id":"Q3077212"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"3236cad670abb20836a95c85e42a14112d41e5a9","datavalue":{"value":{"amount":"+0.89428234","unit":"1"},"type":"quantity"},"datatype":"quantity"}],"P1660":[{"snaktype":"value","property":"P1660","hash":"ba354e87a58191d58d132c60481c945a3234ce85","datavalue":{"value":{"entity-type":"item","numeric-id":6534273,"id":"Q6534273"},"type":"wikibase-entityid"},"datatype":"wikibase-item"}]},"qualifiers-order":["P1659","P1660"],"id":"Q686419$C05CAB6B-B261-43F6-9C70-73AECAF849A2","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"281bddc79129e621838bbfc37e7c4ca69499a35e","datavalue":{"value":{"entity-type":"item","numeric-id":5035074,"id":"Q5035074"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"4ce7dbf36fc174026a131881f2bcdc20293a4ace","datavalue":{"value":{"amount":"+0.892859","unit":"1"},"type":"quantity"},"datatype":"quantity"}],"P1660":[{"snaktype":"value","property":"P1660","hash":"ba354e87a58191d58d132c60481c945a3234ce85","datavalue":{"value":{"entity-type":"item","numeric-id":6534273,"id":"Q6534273"},"type":"wikibase-entityid"},"datatype":"wikibase-item"}]},"qualifiers-order":["P1659","P1660"],"id":"Q686419$16122838-B9E6-496A-85D1-F403C3B101E1","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"dfb5b751900f0944a8d108408ab652f7e16c1901","datavalue":{"value":{"entity-type":"item","numeric-id":3822192,"id":"Q3822192"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"980a3f201c43f8aaf4198b38d69b9ee007a7858f","datavalue":{"value":{"amount":"+0.8900367","unit":"1"},"type":"quantity"},"datatype":"quantity"}],"P1660":[{"snaktype":"value","property":"P1660","hash":"ba354e87a58191d58d132c60481c945a3234ce85","datavalue":{"value":{"entity-type":"item","numeric-id":6534273,"id":"Q6534273"},"type":"wikibase-entityid"},"datatype":"wikibase-item"}]},"qualifiers-order":["P1659","P1660"],"id":"Q686419$181C1214-CD23-42AD-B69F-5DB632216DB7","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"5d84c5e1dbbf4bfd000107f8cb5b38c3bfb90dbc","datavalue":{"value":{"entity-type":"item","numeric-id":3353044,"id":"Q3353044"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"e185aabc1f2838cc47de37fd7c63747a6e6f1e12","datavalue":{"value":{"amount":"+0.88267124","unit":"1"},"type":"quantity"},"datatype":"quantity"}],"P1660":[{"snaktype":"value","property":"P1660","hash":"ba354e87a58191d58d132c60481c945a3234ce85","datavalue":{"value":{"entity-type":"item","numeric-id":6534273,"id":"Q6534273"},"type":"wikibase-entityid"},"datatype":"wikibase-item"}]},"qualifiers-order":["P1659","P1660"],"id":"Q686419$000E0061-4124-4F11-B7E0-3C989778AB22","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"bf7ae3fb34e9f0f64ef42d59886d0b4f4abc3397","datavalue":{"value":{"entity-type":"item","numeric-id":1025536,"id":"Q1025536"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"b09d1db95f578311136c6ea222a217b5f257c761","datavalue":{"value":{"amount":"+0.8798789","unit":"1"},"type":"quantity"},"datatype":"quantity"}],"P1660":[{"snaktype":"value","property":"P1660","hash":"ba354e87a58191d58d132c60481c945a3234ce85","datavalue":{"value":{"entity-type":"item","numeric-id":6534273,"id":"Q6534273"},"type":"wikibase-entityid"},"datatype":"wikibase-item"}]},"qualifiers-order":["P1659","P1660"],"id":"Q686419$C43634B5-C6F8-454B-912A-6B89100F421A","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"a3a9dbc749ab42a1ba59b9b330cf0faabdd76519","datavalue":{"value":{"entity-type":"item","numeric-id":3803147,"id":"Q3803147"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"f7171390adc178e21d7ebc930dee88afafbff0e8","datavalue":{"value":{"amount":"+0.8777966","unit":"1"},"type":"quantity"},"datatype":"quantity"}],"P1660":[{"snaktype":"value","property":"P1660","hash":"ba354e87a58191d58d132c60481c945a3234ce85","datavalue":{"value":{"entity-type":"item","numeric-id":6534273,"id":"Q6534273"},"type":"wikibase-entityid"},"datatype":"wikibase-item"}]},"qualifiers-order":["P1659","P1660"],"id":"Q686419$7C14926B-9A44-4C3F-9CA5-895BB72F835D","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"319a11c78b867858074be110d83ad574b8d03b3f","datavalue":{"value":{"entity-type":"item","numeric-id":2949150,"id":"Q2949150"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"0d2e283e4f20597788733b509eeb119fb788477e","datavalue":{"value":{"amount":"+0.8750295","unit":"1"},"type":"quantity"},"datatype":"quantity"}],"P1660":[{"snaktype":"value","property":"P1660","hash":"ba354e87a58191d58d132c60481c945a3234ce85","datavalue":{"value":{"entity-type":"item","numeric-id":6534273,"id":"Q6534273"},"type":"wikibase-entityid"},"datatype":"wikibase-item"}]},"qualifiers-order":["P1659","P1660"],"id":"Q686419$6F94CB37-CC93-4624-9F8C-8CE0E83A3459","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"e2d510717be9b7f119920af67dd39f349d93eaf6","datavalue":{"value":{"entity-type":"item","numeric-id":1594949,"id":"Q1594949"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"f2f3013722b0b7fab4ceaa3639310c4ed083e02a","datavalue":{"value":{"amount":"+0.8710742","unit":"1"},"type":"quantity"},"datatype":"quantity"}],"P1660":[{"snaktype":"value","property":"P1660","hash":"ba354e87a58191d58d132c60481c945a3234ce85","datavalue":{"value":{"entity-type":"item","numeric-id":6534273,"id":"Q6534273"},"type":"wikibase-entityid"},"datatype":"wikibase-item"}]},"qualifiers-order":["P1659","P1660"],"id":"Q686419$4AC64E5D-3EF8-44D5-944E-2C8B4FD6501F","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"f80b044cd6ee9d11d1354bbab1b6d7d4a6a97883","datavalue":{"value":{"entity-type":"item","numeric-id":4995302,"id":"Q4995302"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"f536bd235c1cf56b6425d188490f20c3bec9329d","datavalue":{"value":{"amount":"+0.8703313","unit":"1"},"type":"quantity"},"datatype":"quantity"}],"P1660":[{"snaktype":"value","property":"P1660","hash":"ba354e87a58191d58d132c60481c945a3234ce85","datavalue":{"value":{"entity-type":"item","numeric-id":6534273,"id":"Q6534273"},"type":"wikibase-entityid"},"datatype":"wikibase-item"}]},"qualifiers-order":["P1659","P1660"],"id":"Q686419$747097EE-B232-4A8B-BF91-3F759C540F80","rank":"normal"}]},"sitelinks":{"mardi":{"site":"mardi","title":"Enumeration of acyclic walks in a graph","badges":[],"url":"https://portal.mardi4nfdi.de/wiki/Enumeration_of_acyclic_walks_in_a_graph"}}}}}