请输入您要查询的字词:

 

单词 Matroid
释义

matroid


A matroidMathworldPlanetmath is a combinatorial structureMathworldPlanetmath whose properties imitate those of linearly independent subsets of a vector space. Notions such as rank and independence (of a subset) have a meaning for any matroid, as does the notion of duality.

1 Definitions of a matroid

A matroid permits several equivalentMathworldPlanetmathPlanetmathPlanetmathPlanetmathPlanetmath formal definitions: two definitionsin terms of a rank function, one in terms of independent subsets, andseveral more. We discuss several definitions below.

First rank definition

Definition 1

A matroid consists of a set E and a function r:P(E)N satisfying the axioms:

  • r1

    For any S𝒫(E), r(S)|S|.

  • r2

    The function r is order-preserving.

  • r3

    The function r satisfies the submodular inequality. That is, for any S, T𝒫(E),

    r(ST)+r(ST)r(S)+r(T).

In this situation, r is called the rank function of the matroid (E,r). If every singleton of E has rank equal to 1, then (E,r) is called a normal matroid.

An isomorphismMathworldPlanetmathPlanetmathPlanetmathPlanetmathPlanetmathPlanetmath of matroids (E,r)(F,s) consists of a bijection f:EF which preserves rank, that is, satisfies s(f(A))=r(A) for all A𝒫(E).

Second rank definition

Definition 2

A matroid consists of a set E and a function r:P(E)N satisfying the axioms:

  • q1

    r()=0.

  • q2

    If xE and S𝒫(E), then r(S{x})-r(S) is either 0 or 1.

  • q3

    If x, yE and S𝒫(E), thenr(S{x})=r(S{y})=r(S) implies r(S{x,y})=r(S).

Independent set definition

Definition 3

A matroid is a pair (E,I) with IP(E) (called the independent setsMathworldPlanetmath of E) satisfying the axioms:

  • i1

    The empty setMathworldPlanetmath is independent.

  • i2

    Every subset of an independent set is independent.

  • i3

    For any UE, any two subsets of U which are maximal with respect to membership in have the same cardinality.

The matroid (E,I) is normal if every singleton in E is independent.

Base definition

Definition 4

A matroid is a pair (E,B) with BP(E) (called the bases of E) a subset of P(E) satisfying the axioms:

  • b1

    E has at least one base.

  • b2

    The proper subsetsMathworldPlanetmathPlanetmath of a base are not bases.

  • b3

    If S and T are bases and xES, then for some yET, the set (S{x}){y} is a base.

The matroid (E,) is called normal if each singleton of E is contained in a base of E.

Closure definition

Definition 5

A matroid consists of a set E and a function cl:P(E)P(E), called the closure operatorPlanetmathPlanetmathPlanetmath, satisfying the axioms:

  • cl1

    Any subset of E is contained in its closureMathworldPlanetmath.

  • cl2

    If Scl(T) then cl(S)cl(T).

  • cl3

    If x is in the closure of S{y} but not that of S, then y is in the closure of S{x}.

The closure operator is sometimes also called the span mapping of the matroid. In this case cl(A) is called the span of A.

The matroid (E,cl) is normal if the empty set is its own closure.

Circuit definition

Definition 6

A matroid is a pair (E,C) with CP(E) (called the circuitsMathworldPlanetmath of E) satisfying the axioms:

  • c1

    The empty set is not a circuit.

  • c2

    The proper supersets of a circuit are not circuits.

  • c3

    If x is in the intersectionMathworldPlanetmathPlanetmath of two distinct circuits S and T, then there is a circuit UST which does not contain x.

The matroid (E,𝒞) is normal if no singleton of E is a circuit.

Combinatorial optimization definition

There’s yet another definition of matroids from “Combinatorial Optimization” by Papadimitriou and Steiglitz. pp. 280-285.

It requires three definitions to generate their definition of matroids. These are more or less grabbed from the book above.

A subset system (E,g) is a finite setMathworldPlanetmath E with g a collectionMathworldPlanetmath of subsets of E closed under inclusion, meaning that if Ag, and BA, then Bg.

Definition 2: The “combinatorial optimization problem” (nonstandard term used in book) is as follows. Let (E,g) be a subset system and weight w, a nonnegative real function on E. Find the subset in g with the largest total weight.

Definition 3: Let (E,g) be a subset system and w, a weight function defined as above to give the “combinatorial optimization problem”. The greedy algorithm for construction of a subset I in g is as follows. Start with I being the empty set. Take the next highest weight element, e in E (w(e) ¿= w(f) for all f in E). If the union of I and e is in g, then add element e to I. Repeat until you exhaust all elements of E.

Now we have the definition of a matroid.

Definition 4:Let M=(E,g) be a subset system. M is a “matroid” if the greedy algorithm correctly solves the ”combinatorial optimization problem” for any weight function associated with M.

2 Equivalence of the definitions

It would take several pages to spell out what is a circuit in terms of rank,and likewise for each other possible pair of the alternative defining notions,and then to prove that the various sets of axioms unambiguously define thesame structure.So let me sketch just one example: the equivalence of Definitions 1 (onrank) and 6 (on circuits).Assume first the conditions in Definition 1.Define a circuit as a minimalPlanetmathPlanetmath subset A of 𝒫(E) having the propertyr(A)<|A|.With a little effort, we verify the axioms (c1)-(c3).Now assume (c1)-(c3), and let r(A) be the largestinteger n such that A has a subset B for which

B contains no element of C

n=|B|.

One now proves (r1)-(r3).Next, one shows that if we define C in terms ofr, and then another rank function s in terms of C, we end up withs=r.The equivalence of (r*) and (c*) is easy enough as well.

3 Examples of matroids

Let V be a vector space over a field k, and let E be a finite subset ofV.For SE, let r(S) be the dimensionMathworldPlanetmathPlanetmath of the subspaceMathworldPlanetmathPlanetmath of Vgenerated by S.Then (E,r) is a matroid.Such a matroid, or one isomorphicto it, is said to be representable over k.The matroid is normal iff 0E.There exist matroids which are not representable over any field.

The second example of a matroid comes from graph theoryMathworldPlanetmath.The following definition will be rather informal, partly because theterminology of graph theory is not very well standardised.For our present purpose, a graph consistsof a finite set V, whose elements are called vertices, plus a set E oftwo-element subsets of V, called edges.A circuit in the graph is a finite set of at least three edges which canbe arranged in a cycle:

{a,b},{b,c},{y,z},{z,a}

such that the vertices a,b,z are distinct.With circuits thus defined, E satisfies the axioms in Definition 6,and is thus a matroid, and in fact a normal matroid.(The definition is easily adjusted to permit graphs with loops, whichdefine non-normal matroids.)Such a matroid, or one isomorphic to it, is called “graphic”.

Let E=AB be a finite set, where A and B are nonempty and disjoint.Let G a subset of A×B.We get a “matching” matroid on E as follows.Each element of E defines a “line” which is a subset(a row or column) of the set A×B.Let us call the elements of G “points”.For any SE let r(S)be the largest number n such that for some set of points P:

|P|=n

– No two points of P are on the same line

– Any point of P is on a line defined by an element of S.

One can prove (it is not trivial) that r is the rank function ofa matroid on E.That matroid is normal iff every line contains at least one point.Matching matroids participate in combinatorics, inconnection with results on “transversals”, such as Hall’s marriagetheoremMathworldPlanetmath.

4 The dual of a matroid

PropositionPlanetmathPlanetmathPlanetmath: Let E be a matroid and r its rank function.Define a mapping s:β(E) by

s(A)=|A|-r(E)+r(E-A).

Then the pair (E,s) is a matroid (called the dual of (E,r).

We leave the proof as an exercise.Also, it is easy to verify that thedual of the dual is the original matroid.A circuit in (E,s) is alsoreferred to as a cocircuit in (E,r).There is a notion of cobasis also, and cospan.

If the dual of E is graphic, E is called cographic.This notion ofduality agrees with the notion of same name in the theory of planargraphsMathworldPlanetmath (and likewise in linear algebra): given a plane graph, the dualof its matroid is the matroid of the dual graph.A matroid that is bothgraphic and cographic is called planar, and various criteria forplanarity of a graph can be extended to matroids.The notion oforientability can also be extended from graphs to matroids.

5 Binary matroids

A matroid is said to be binary if it is representable over the field oftwo elements.There are several other (equivalent) characterisations of a binarymatroid (E,r), such as:

– The symmetric differenceMathworldPlanetmathPlanetmath of any family of circuits is the union ofa family of pairwise disjoint circuits.

– For any circuit C and cocircuit D, we have |CD|0(mod2).

Any graphic matroid is binary.The dual of a binary matroid is binary.

6 Miscellaneous

The definition of the chromatic polynomial of a graph,

χ(x)=FE(-1)|F|xr(E)-r(F),

extends without change to any matroid.This polynomial has something to say about the decomposibility ofmatroids into simpler ones.

Also on the topic of decomposibility, matroids have a sort ofstructure theory, in terms of what are called minors and separators.That theory, due to Tutte, goes by inductionMathworldPlanetmath; roughly speaking,it is an adaptation of the old algorithmsMathworldPlanetmath for puttinga matrix into a canonical form.

Along the same lines are several theorems on “basis exchange”, such asthe following.Let E be a matroid and let

A={a1,,an}
B={b1,,bn}

be two (equipotent) bases of E.There exists a permutationMathworldPlanetmath ψ of the set{1,,n} such that, for every m from 0 to n,

{a1,,am,bψ(m+1),,bψ(n)}

is a basis of E.

7 Further reading

A good textbook is:

James G. Oxley, Matroid Theory,Oxford University Press, New York etc., 1992

plus the updates-and-errata file at Dr. Oxley’shttp://www.math.lsu.edu/ oxleywebsite.

The chromatic polynomial is not discussed in Oxley, but see e.g.http://www.math.binghamton.edu/zaslav/MatroidsZaslavski.

随便看

 

数学辞典收录了18232条数学词条,基本涵盖了常用数学知识及数学英语单词词组的翻译及用法,是数学学习的有利工具。

 

Copyright © 2000-2023 Newdu.com.com All Rights Reserved
更新时间:2025/5/4 8:54:14