매트로이드

수학노트
둘러보기로 가기 검색하러 가기

노트

말뭉치

  1. A matroid M is a pair (E, C) consisting of a nite set E, called the ground set, and a set C of subsets of E, called circuits, that obey the following three conditions.[1]
  2. In a matroid M , we often write E(M ) for the ground set and C(M ) for the set of circuits, especially when several matroids are being considered.[1]
  3. Let G be a graph with edge set E and C be the set of edge sets of cycles of G. Then (E, C) is a matroid.[1]
  4. The matroid whose existence is asserted there is called the cycle matroid of the graph G and is denoted by M (G).[1]
  5. Every ag B1 ... Bs with Bi a basis of Mi is in F. The relation is obtained by considering ag matroid polytopes and lattice polytopes representing a toric variety.[2]
  6. Denition (Dual of a matroid) Let M = (E , B) be a matroid.[2]
  7. A regular (i.e. representable over every eld) matroid is graphic if and only if it has no minor isomorphic to M (K5) or M (K3,3).[2]
  8. 9 A brief detour on representability Previously, we saw that U 2 matroid which is not representable.[2]
  9. Introduction to Matroids A matroid is a structure that generalizes the properties of indepen- dence.[3]
  10. There are several ways to de(cid:12)ne a matroid, each relate to the concept of independence.[3]
  11. This paper will focus on the the de(cid:12)nitions of a matroid in terms of bases, the rank function, independent sets and cycles.[3]
  12. The four de(cid:12)nitions of a matroid introduced in this paper are equiv- alent to each other.[3]
  13. Roughly speaking, a matroid is a finite set together with a generalization of a concept from linear algebra that satisfies a natural set of properties for that concept.[4]
  14. A matroid can be defined in terms of bases.[5]
  15. A matroid consists of a ground set as well as a set of bases which is a nonempty subset of the power set of the ground set.[5]
  16. The answer is yes, and the framework that enables us to do this is called a matroid.[6]
  17. That is, if we can phrase the problem we’re trying to solve as a matroid, then the greedy algorithm is guaranteed to be optimal.[6]
  18. There is also a similar concept of an oriented matroid; every oriented matroid has an underlying matroid.[7]
  19. Proposition Any two bases of a matroid X X have the same cardinality, provided that one of them is finite.[7]
  20. The cardinality of such a basis is called of course the dimension of the matroid.[7]
  21. Clearly then a finite matroid has a well-defined dimension.[7]
  22. The word matroid was coined by Whitney in 1935 in his landmark paper "On the abstract properties of linear dependence".[8]
  23. In defining a matroid Whitney tried to capture the fundamental properties of dependence that are common to graphs and matrices.[8]
  24. Almost simultaneously, Birkhoff showed that a matroid can be interpreted as a geometric lattice.[8]
  25. This page has a chronological list of matroid books including collections of papers, applications and generalizations.[8]
  26. A matroid, M , dened by independent sets comes with two pieces.[9]
  27. Let us check that M = (E, I) is a matroid.[9]
  28. After a lot of painful checking, we nd that the M we dened above is actually a matroid.[9]
  29. This matroid has another name: the uniform matroid U2,4.[9]
  30. There are two main entry points to Sage’s matroid functionality.[10]
  31. This function attempts to interpret its arguments to create an appropriate matroid.[10]
  32. graph – A graph, whose edges form the elements of the matroid.[10]
  33. matroid – An object that is already a matroid.[10]
  34. E.1 Denitions Many problems that can be correctly solved by greedy algorithms can be described in terms of an abstract combinatorial object called a matroid.[11]
  35. An independent set is called a basis of the matroid if it is not a proper subset of another independent set.[11]
  36. The exchange property implies that every basis of a matroid has the same cardinality.[11]
  37. Most of this terminology is justied by Whitneys original example: Linear matroid: Let A be any n m matrix.[11]
  38. In the language of partially ordered sets, a finite matroid is equivalent to a geometric lattice.[12]
  39. Matroid theory borrows extensively from the terminology of both linear algebra and graph theory, largely because it is the abstraction of various notions of central importance in these fields.[12]
  40. A maximal independent set—that is, an independent set that becomes dependent upon adding any element of E {\displaystyle E} —is called a basis for the matroid.[12]
  41. The collections of dependent sets, of bases, and of circuits each have simple properties that may be taken as axioms for a matroid.[12]
  42. This survey paper introduces matroid theory, presents some of the main theorems in the subject, and identies some of the major problems of current research interest.[13]
  43. This survey of matroid theory will assume only that the reader is familiar with the basic concepts of linear algebra.[13]
  44. In Section 2, Whitneys denition of a matroid is given, some basic classes of examples of matroids are introduced, and some important questions are identied.[13]
  45. The set E and the members of I are the ground set and independent sets of this matroid.[13]
  46. The Matroid product enables non-software organizations in enterprise to harness the power of software-defined sensors.[14]
  47. With the Matroid product, we set a new standard for ease of use in deploying sensors.[14]
  48. Once a detector is developed, Matroid can search any live stream or recorded video, providing real time notifications when the object of interest has been detected.[14]
  49. Customers use Matroid in construction, manufacturing, security, media, retail and other industries.[14]
  50. The polymatroid matching problem, also known as the matchoid problem or the matroid parity problem, is polynomially unsolvable in general but solvable for linear matroids.[15]
  51. As this book is being written, a large collection of deep matroid theorems already exists.[16]
  52. So I'd like to know, please, what specific results a matroid theory partisan would likely cite as the best demonstrations of the power of matroid theory within the larger arena of mathematics.[17]
  53. Matroid theory examines and answers questions like these.[18]
  54. This book falls into two parts: the first provides a comprehensive introduction to the basics of matroid theory, while the second treats more advanced topics.[18]
  55. We saw in the previous section that both problems, \((P_{\le k})\) and \((P_{\ge k})\), can be solved in strongly polynomial time via a weighted matroid intersection algorithm.[19]
  56. Note that this problem can be solved with a matroid greedy algorithm.[19]
  57. A. Frank proved the following result about sequences of moves, to show correctness of the weighted matroid intersection algorithm.[19]
  58. Introduction A matroid is a combinatorial structure that possesses important combinatorial properties of a wide variety of math emati cal structures.[20]
  59. J arc called the independent sets of the matroid.[20]
  60. J are called the bases of the matroid.[20]
  61. Set ill equivalently defines a matroid on E .[20]

소스

  1. ↑ 1.0 1.1 1.2 1.3 Briefly, what is a matroid?
  2. ↑ 2.0 2.1 2.2 2.3 Matroid theory
  3. ↑ 3.0 3.1 3.2 3.3 Matroid theory
  4. ↑ Matroid -- from Wolfram MathWorld
  5. ↑ 5.0 5.1 Wiktionary
  6. ↑ 6.0 6.1 When Greedy Algorithms are Perfect: the Matroid
  7. ↑ 7.0 7.1 7.2 7.3 matroid in nLab
  8. ↑ 8.0 8.1 8.2 8.3 Matroid Theory
  9. ↑ 9.0 9.1 9.2 9.3 What is a matroid?
  10. ↑ 10.0 10.1 10.2 10.3 Matroid construction — Matroid Theory
  11. ↑ 11.0 11.1 11.2 11.3 The problem is that we attempt to solve the simplest questions cleverly,
  12. ↑ 12.0 12.1 12.2 12.3 Wikipedia
  13. ↑ 13.0 13.1 13.2 13.3 What is a matroid?
  14. ↑ 14.0 14.1 14.2 14.3 Matroid Completes $20 Million Series B Financing to Expand into Manufacturing and Industrial IOT
  15. ↑ Matroid matching and some applications
  16. ↑ Truemper: Matroid Decomposition
  17. ↑ What are the external triumphs of matroid theory?
  18. ↑ 18.0 18.1 Matroid Theory
  19. ↑ 19.0 19.1 19.2 Matroid bases with cardinality constraints on the intersection
  20. ↑ 20.0 20.1 20.2 20.3 Jou rnal of research of the na t ional bureau of standa r ds-b. mathematical sciences

메타데이터

위키데이터

Spacy 패턴 목록

  • [{'LOWER': 'matroid'}]
원본 주소 "https://wiki.mathnt.net/index.php?title=매트로이드&oldid=53016"