{"entities":{"Q41246":{"pageid":41302,"ns":120,"title":"Item:Q41246","lastrevid":105427802,"modified":"2026-10-09T10:08:25Z","type":"item","id":"Q41246","labels":{"en":{"language":"en","value":"Maximum Cardinality Matching"}},"descriptions":{"en":{"language":"en","value":"AFP entry Max-Card-Matching"}},"aliases":{},"claims":{"P13":[{"mainsnak":{"snaktype":"value","property":"P13","hash":"83ce809bc85116f62f878760f679a4e17a66fe58","datavalue":{"value":"29532","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q41246$5A7EFEB2-41E3-484D-B7FD-A0C1FF6684D7","rank":"normal"}],"P1460":[{"mainsnak":{"snaktype":"value","property":"P1460","hash":"908c3454b3659c4b140ccce33c5aee31081edc8d","datavalue":{"value":{"entity-type":"item","numeric-id":5976450,"id":"Q5976450"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q41246$6E249298-B77D-4E16-8A99-BA3536A277C7","rank":"normal"}],"P29":[{"mainsnak":{"snaktype":"value","property":"P29","hash":"55cb1dea10a5ef17ec54490552e57ea4517d15f0","datavalue":{"value":"https://www.isa-afp.org/entries/Max-Card-Matching.html","type":"string"},"datatype":"url"},"type":"statement","id":"Q41246$B9EF21D5-04B0-4F7E-B622-BFD350FA3319","rank":"normal"}],"P226":[{"mainsnak":{"snaktype":"value","property":"P226","hash":"acf10290b955a69659a681d98822944f91bbad9e","datavalue":{"value":"68","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q41246$F7901B80-E673-45DE-B462-C94E4975950B","rank":"normal"}],"P1458":[{"mainsnak":{"snaktype":"value","property":"P1458","hash":"ce995af0d54f8ab3594278c155d6ae4d6e3a6165","datavalue":{"value":{"entity-type":"item","numeric-id":16614,"id":"Q16614"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q41246$0CC9D056-CBDA-4F47-84A6-41C22A9453F9","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1458","hash":"e600fcf4c16bf9bbec6afc7a64801eb6824b335c","datavalue":{"value":{"entity-type":"item","numeric-id":40264,"id":"Q40264"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q41246$F4B4B27D-8817-4C72-81AF-B3854D9B2CBA","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1458","hash":"1dd50e6d12db6d69b44d98a789719c63bc20b24d","datavalue":{"value":{"entity-type":"item","numeric-id":13265,"id":"Q13265"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q41246$714CA9E5-73CA-4100-A29E-FB49BCA9BBDA","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1458","hash":"bb05cb23794774f62a8e4aa4de610af231973a1d","datavalue":{"value":{"entity-type":"item","numeric-id":40327,"id":"Q40327"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q41246$2A9EF286-42A9-49C6-AC73-EACD92946296","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1458","hash":"3e9c336168e17650e6c38b2eaa0f70237b2e636e","datavalue":{"value":{"entity-type":"item","numeric-id":40295,"id":"Q40295"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q41246$4BC74075-06DA-4359-A1D6-F9DC34E60DF6","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1458","hash":"4a7fa684cfde41f7d9fb30a83470901eeb256b85","datavalue":{"value":{"entity-type":"item","numeric-id":43947,"id":"Q43947"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q41246$64CE2DEC-443C-4B67-A815-3CC81906ACC1","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1458","hash":"61d0c0612cc30c9c51b93ddaf1f78ee1ae75f9fe","datavalue":{"value":{"entity-type":"item","numeric-id":18676,"id":"Q18676"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q41246$7692AFFE-2A1F-4456-8F12-5B820542EEC2","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1458","hash":"cc4eff68b160f30b8d66dfcb610a0ea7a927079b","datavalue":{"value":{"entity-type":"item","numeric-id":17039,"id":"Q17039"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q41246$A2FF29F9-1679-4FF9-9589-5CFFDD37AADD","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1458","hash":"cc41d9364226bfa8139f8dbc43b1b77967245f13","datavalue":{"value":{"entity-type":"item","numeric-id":17631,"id":"Q17631"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q41246$DF255F8A-D86E-41FA-B399-FDDC47BD84EA","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1458","hash":"a78d10351f0710c61eb19af8201147471568ba3a","datavalue":{"value":{"entity-type":"item","numeric-id":16796,"id":"Q16796"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q41246$0F41DD3E-71D6-4F79-B369-7BAA0E73A52B","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1458","hash":"07eb0f28b45c8f9b5cf112bbf02e95717fb938ca","datavalue":{"value":{"entity-type":"item","numeric-id":25202,"id":"Q25202"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q41246$F9514C2D-5604-4EF6-BD9C-C8FF5E14835E","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1458","hash":"4d7f4b76492a75780585d40fb718d00d42a05322","datavalue":{"value":{"entity-type":"item","numeric-id":19570,"id":"Q19570"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q41246$DF24CD32-560F-4528-BF30-FBBB8263DAD3","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1458","hash":"1286389c58ecdb69c422604e3e1f0dbe5e0370f0","datavalue":{"value":{"entity-type":"item","numeric-id":15691,"id":"Q15691"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q41246$E4D94085-B4F8-4629-A2CA-D94E223A30AB","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1458","hash":"144f0221487b5ba035abaca0f440960a9e47efeb","datavalue":{"value":{"entity-type":"item","numeric-id":27113,"id":"Q27113"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q41246$A84EC4B8-F53A-44A5-A4A0-6623C5E7DB05","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1458","hash":"e3e9bb7b329ec8e71fcb8b28c9805dd4509dedab","datavalue":{"value":{"entity-type":"item","numeric-id":19731,"id":"Q19731"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q41246$E1C2EBEF-6B65-4D1F-9169-850BCDE81E4D","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1458","hash":"bb0bb7298ee3f535da596bef22c2f5c7449c7dc4","datavalue":{"value":{"entity-type":"item","numeric-id":19271,"id":"Q19271"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q41246$5AF83110-98F4-4EE0-8977-F6AEE957DFFC","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1458","hash":"a2a767ccd0e9bdc5b1b4a2069a6679f9340a857a","datavalue":{"value":{"entity-type":"item","numeric-id":14275,"id":"Q14275"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q41246$1BC90C2A-309F-4389-AAAC-E7382D1C9658","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1458","hash":"ff80b41d03c65073c007c903a317be0a9c94293e","datavalue":{"value":{"entity-type":"item","numeric-id":13958,"id":"Q13958"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q41246$B4021423-22C0-4C0D-9617-E5EFFAF546C0","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1458","hash":"ecda3e6d8e971c0b93d4cf3afb41990e853f830f","datavalue":{"value":{"entity-type":"item","numeric-id":13212,"id":"Q13212"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q41246$0D28A133-D15D-4286-A27B-38781CD93650","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1458","hash":"d598055e76e7c072cae9308bcd9069cd8e8780d2","datavalue":{"value":{"entity-type":"item","numeric-id":13169,"id":"Q13169"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q41246$0ABD22FD-6843-4BC2-8BE9-90BD54DCC654","rank":"normal"}],"P205":[{"mainsnak":{"snaktype":"value","property":"P205","hash":"57cf29b4361e85cf90f5f6b42f67cf460348012a","datavalue":{"value":"https://isa-afp.org/entries/Max-Card-Matching.html","type":"string"},"datatype":"url"},"type":"statement","id":"Q41246$B86DBEFE-E5C3-4E67-AC8C-F339C860EDD3","rank":"normal"}],"P43":[{"mainsnak":{"snaktype":"value","property":"P43","hash":"55b0fc3dc61297337ef172ccc1d73223c8496fb0","datavalue":{"value":"Christine Rizkallah","type":"string"},"datatype":"string"},"type":"statement","id":"Q41246$FAA6DF55-5118-41E0-AA7A-6F9B2C02B764","rank":"normal"}],"P1448":[{"mainsnak":{"snaktype":"value","property":"P1448","hash":"da7439d65f426a653e094b572547e3ead92e0456","datavalue":{"value":"A matching in a graph G is a subset M of the edges of G such that no two share an endpoint. A matching has maximum cardinality if its cardinality is at least as large as that of any other matching. An odd-set cover OSC of a graph G is a labeling of the nodes of G with integers such that every edge of G is either incident to a node labeled 1 or connects two nodes labeled with the same number i \u2265 2 . This article proves Edmonds theorem: Let M be a matching in a graph G and let OSC be an odd-set cover of G . For any i \u2265 0 , let n(i) be the number of nodes labeled i . If |M| = n(1) + \u2211 i \u2265 2 (n(i) div 2) , then M is a maximum cardinality matching.","type":"string"},"datatype":"string"},"type":"statement","id":"Q41246$9AD103B5-5E26-4682-8AA6-4F562090BCCC","rank":"normal"}],"P28":[{"mainsnak":{"snaktype":"value","property":"P28","hash":"55549e65a69e36a60dff96c251edfdfdcb488c38","datavalue":{"value":{"time":"+2011-07-21T00:00:00Z","timezone":0,"before":0,"after":0,"precision":11,"calendarmodel":"http://www.wikidata.org/entity/Q1985727"},"type":"time"},"datatype":"time"},"type":"statement","id":"Q41246$A2FF5D20-2E53-4919-ADA2-E97C6AA7449D","rank":"normal"}],"P159":[{"mainsnak":{"snaktype":"value","property":"P159","hash":"f38f61ef9c542ff1410b569de37e5b96d4fe602e","datavalue":{"value":{"text":"Maximum Cardinality Matching","language":"en"},"type":"monolingualtext"},"datatype":"monolingualtext"},"type":"statement","id":"Q41246$440C9D09-4644-4BBB-B33A-C924F44ECB2B","rank":"normal"}],"P223":[{"mainsnak":{"snaktype":"value","property":"P223","hash":"7bd8b848f40aaa3f56b8b15df38fbe662aeb1afa","datavalue":{"value":{"entity-type":"item","numeric-id":5516087,"id":"Q5516087"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q41246$A58C3262-6B1F-4E81-8A97-B8B116A3A949","rank":"normal"}],"P37":[{"mainsnak":{"snaktype":"value","property":"P37","hash":"9a21a8eebe97539644aa32b24dda137c12e751dc","datavalue":{"value":{"entity-type":"item","numeric-id":40327,"id":"Q40327"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q41246$8C27F0ED-8308-4596-B61F-9069DC11A147","rank":"normal"}],"P2651":[{"mainsnak":{"snaktype":"value","property":"P2651","hash":"f3718ba60fb3ca54d1e75bc16696ddd7ca207e99","datavalue":{"value":{"entity-type":"item","numeric-id":7360827,"id":"Q7360827"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q41246$732A6FE0-98A9-4C37-9E1F-7A75629CC3FA","rank":"normal"}]},"sitelinks":{"mardi":{"site":"mardi","title":"Maximum Cardinality Matching","badges":[],"url":"https://portal.mardi4nfdi.de/wiki/Maximum_Cardinality_Matching"}}}}}