Matroid - Matroid

İçinde kombinatorik bir dalı matematik, bir matroid /ˈmeɪtrɔɪd/ kavramını özetleyen ve genelleyen bir yapıdır doğrusal bağımsızlık içinde vektör uzayları. Bir matroid tanımlamanın birçok eşdeğer yolu vardır aksiyomatik olarak şu açılardan en önemlisi: bağımsız kümeler; bazlar veya devreler; sıralama işlevleri; kapatma operatörleri; ve kapalı setler veya daireler. Dilinde kısmen sıralı kümeler, sonlu bir matroid, bir geometrik kafes.

Matroid teorisi, büyük ölçüde şu terminolojiden ödünç alır: lineer Cebir ve grafik teorisi büyük ölçüde bu alanlarda merkezi öneme sahip çeşitli kavramların soyutlaması olduğu için. Matroidler şu uygulamalarda bulundu: geometri, topoloji, kombinatoryal optimizasyon, ağ teorisi ve kodlama teorisi.^[1][2]

Tanım

Pek çok eşdeğer var (kriptomorfik ) bir (sonlu) matroidi tanımlama yolları.^[3]

Bağımsız setler

Bağımsızlık açısından sonlu bir matroid ${ displaystyle M}$ bir çift ${ displaystyle (E, { mathcal {I}})}$, nerede ${ displaystyle E}$ bir Sınırlı set (aradı zemin seti) ve ${ displaystyle { mathcal {I}}}$ bir aile nın-nin alt kümeler nın-nin ${ displaystyle E}$ (aradı bağımsız kümeler) aşağıdaki özelliklere sahip:^[4]

(I1) boş küme bağımsızdır, yani ${ mathcal {I}}} içinde { displaystyle emptyset$. Alternatif olarak, en az bir alt kümesi ${ displaystyle E}$ bağımsızdır, yani ${ displaystyle { mathcal {I}} neq emptyset}$.

(I2) Bağımsız bir kümenin her alt kümesi bağımsızdır, yani her biri için ${ displaystyle A ' subseteq A subseteq E}$, Eğer ${ mathcal {I}}} içinde { displaystyle A$ sonra ${ mathcal {I}}} içinde { displaystyle A '$. Bu bazen denir kalıtsal mülkiyet, ya da aşağı kapalı Emlak.

(I3) Eğer ${ displaystyle A}$ ve ${ displaystyle B}$ iki bağımsız kümedir (yani, her küme bağımsızdır) ve ${ displaystyle A}$ daha fazla unsura sahip ${ displaystyle B}$o zaman var ${ displaystyle x , A ters eğik çizgi B}$ öyle ki ${ displaystyle B fincan {x }}$ içinde ${ displaystyle { mathcal {I}}}$. Bu bazen denir artırma özelliği ya da bağımsız küme değişim özelliği.

İlk iki özellik, bir kombinatoryal yapıyı tanımlar. bağımsızlık sistemi (veya soyut basit kompleks ).

Bazlar ve devreler

Zemin kümesinin bir alt kümesi ${ displaystyle E}$ bağımsız olmayan denir bağımlı. Bir maksimum bağımsız küme - yani, herhangi bir öğenin eklenmesine bağımlı hale gelen bağımsız bir küme. ${ displaystyle E}$- denir temel matroid için. Bir devre matroid içinde ${ displaystyle M}$ minimum bağımlı alt kümesidir ${ displaystyle E}$- yani, uygun alt kümelerinin tümü bağımsız olan bağımlı bir küme. Terminoloji ortaya çıkar çünkü grafik matroidler ilgili grafiklerdeki döngülerdir.^[4]

Bağımlı kümeler, bazlar veya bir matroidin devreleri matroidi tamamen karakterize eder: bir küme, ancak ve ancak bağımlı değilse, ancak ve ancak bir temelin alt kümesiyse ve eğer ve ancak varsa bir devre içermez. Bağımlı kümeler, bazlar ve devre koleksiyonlarının her biri, bir matroid için aksiyomlar olarak alınabilecek basit özelliklere sahiptir. Örneğin, bir matroid tanımlanabilir ${ displaystyle M}$ çift ​​olmak ${ displaystyle (E, { mathcal {B}})}$, nerede ${ displaystyle E}$ eskisi gibi sonlu bir kümedir ve ${ displaystyle { mathcal {B}}}$ alt kümelerinin bir koleksiyonudur ${ displaystyle E}$, aşağıdaki özelliklere sahip "bazlar" olarak adlandırılan:^[4]

(B1) ${ displaystyle { mathcal {B}}}$ boş değil.

(B2) Eğer ${ displaystyle A}$ ve ${ displaystyle B}$ farklı üyeleridir ${ displaystyle { mathcal {B}}}$ ve ${ displaystyle a in A setminus B}$sonra bir eleman var ${ displaystyle b in B setminus A}$ öyle ki ${ displaystyle (A setminus {a }) cup {b } { mathcal {B}}} içinde$. Bu özelliğe temel değişim mülkü.

Temel değişim mülkünden, hiçbir üyenin ${ displaystyle { mathcal {B}}}$ başka birinin uygun bir alt kümesi olabilir.

Rank fonksiyonları

Matroid teorisinin temel bir sonucudur, benzer bir teoremine doğrudan benzer doğrusal cebirdeki bazlar, bir matroidin herhangi iki temelinin ${ displaystyle M}$ aynı sayıda öğeye sahip. Bu numaraya sıra nın-nin${ displaystyle M}$. Eğer ${ displaystyle M}$ matroid üzerinde ${ displaystyle E}$, ve ${ displaystyle A}$ alt kümesidir ${ displaystyle E}$, sonra bir matroid ${ displaystyle A}$ bir alt kümesi dikkate alınarak tanımlanabilir ${ displaystyle A}$ bağımsız olmak, ancak ve ancak bağımsız ise ${ displaystyle M}$. Bu, hakkında konuşmamızı sağlar alt matroidler ve herhangi bir alt kümesinin sıralaması hakkında ${ displaystyle E}$. Bir alt kümenin sıralaması ${ displaystyle A}$ tarafından verilir sıralama işlevi ${ displaystyle r (A)}$ Aşağıdaki özelliklere sahip olan matroidin:^[4]

• Sıra işlevinin değeri her zaman negatif değildir tamsayı.
• Herhangi bir alt küme için ${ displaystyle A alt küme E}$, sahibiz ${ Displaystyle r (A) leq | A |}$.
• Herhangi iki alt küme için ${ displaystyle A, B alt küme E}$, sahibiz: ${ Displaystyle r (A fincan B) + r (A cap B) leq r (A) + r (B)}$. Yani, rütbe bir alt modüler işlev.
• Herhangi bir set için ${ displaystyle A}$ ve eleman ${ displaystyle x}$, sahibiz: ${ Displaystyle r (A) leq r (A fincan {x }) leq r (A) +1}$. İlk eşitsizlikten, daha genel olarak şunu izler: ${ displaystyle A subseteq B subseteq E}$, sonra ${ Displaystyle r (A) leq r (B) leq r (E)}$. Yani, rütbe bir tekdüze işlev.

Bu özellikler, sonlu bir matroidin alternatif tanımlarından biri olarak kullanılabilir: ${ displaystyle (E, r)}$ bu özellikleri, ardından matroidin bağımsız kümelerini karşılar. ${ displaystyle E}$ bu alt kümeler olarak tanımlanabilir ${ displaystyle A}$ nın-nin ${ displaystyle E}$ ile ${ displaystyle r (A) = | A |}$. Dilinde kısmen sıralı kümeler böyle bir matroid yapısı, geometrik kafes kimin elemanları alt kümelerdir ${ displaystyle A alt küme M}$, kısmen dahil edilerek sıralanmıştır.

Fark ${ displaystyle | A | -r (A)}$ denir geçersizlik alt kümenin ${ displaystyle A}$. Kaldırılması gereken minimum öğe sayısıdır ${ displaystyle A}$ bağımsız bir set elde etmek için. Geçersizliği ${ displaystyle E}$ içinde ${ displaystyle M}$ geçersizliği denir ${ displaystyle M}$. Fark ${ displaystyle r (E) -r (A)}$ bazen denir corank alt kümenin ${ displaystyle A}$.

Kapatma operatörleri

İzin Vermek ${ displaystyle M}$ sonlu bir sette matroid olmak ${ displaystyle E}$, rank işlevi ile ${ displaystyle r}$ yukarıdaki gibi. kapatma (veya açıklık) ${ displaystyle operatöradı {cl} (A)}$ bir alt kümenin ${ displaystyle A}$ nın-nin ${ displaystyle E}$ set

${ displaystyle operatorname {cl} (A) = { Bigl {} x in E orta r (A) = r { bigl (} A cup {x } { bigr)} { Bigr }}}$.

Bu bir kapatma operatörü ${ displaystyle operatorname {cl}: { mathcal {P}} (E) - { mathcal {P}} (E)}$ nerede ${ displaystyle { mathcal {P}}}$ gösterir Gücü ayarla, aşağıdaki özelliklere sahip:

• Tüm alt kümeler için ${ displaystyle X}$ nın-nin ${ displaystyle E}$, ${ displaystyle X subseteq operatöradı {cl} (X)}$.
• Tüm alt kümeler için ${ displaystyle X}$ nın-nin ${ displaystyle E}$, ${ displaystyle operatöradı {cl} (X) = operatöradı {cl} ( operatöradı {cl} (X))}$.
• Tüm alt kümeler için ${ displaystyle X}$ ve ${ displaystyle Y}$ nın-nin ${ displaystyle E}$ ile ${ displaystyle X subseteq Y}$, ${ displaystyle operatorname {cl} (X) subseteq operatorname {cl} (Y)}$.
• Tüm unsurlar için ${ displaystyle a}$, ve ${ displaystyle b}$ nın-nin ${ displaystyle E}$ ve tüm alt kümeler ${ displaystyle Y}$ nın-nin ${ displaystyle E}$, Eğer ${ displaystyle a in operatorname {cl} (Y cup {b }) setminus operatorname {cl} (Y)}$ sonra ${ displaystyle b in operatorname {cl} (Y cup {a }) setminus operatorname {cl} (Y)}$.

Bu özelliklerin ilk üçü, bir kapatma operatörünün tanımlayıcı özellikleridir. Dördüncü bazen denir Mac Lane –Steinitz mal değişimi. Bu özellikler matroidin başka bir tanımı olarak alınabilir: her fonksiyon ${ displaystyle operatorname {cl}: { mathcal {P}} (E) - { mathcal {P}} (E)}$ bu özelliklere itaat eden bir matroid belirler.^[4]

Daireler

Kapanışı kendisine eşit olan bir setin kapalıveya a düz veya alt uzay matroidin.^[5] Bir set kapalıysa maksimum sıralaması için, diğer herhangi bir öğenin kümeye eklenmesi sıralamayı artıracağı anlamına gelir. Bir matroidin kapalı setleri, bir örtücü bölme özelliği ile karakterize edilir:

• Bütün nokta seti ${ displaystyle E}$ kapalı.
• Eğer ${ displaystyle S}$ ve ${ displaystyle T}$ daireler, o zaman ${ displaystyle S cap T}$ bir daire.
• Eğer ${ displaystyle S}$ bir düz, sonra her bir öğesi ${ displaystyle E setminus S}$ tam olarak dairelerden birinde ${ displaystyle T}$ o örtmek ${ displaystyle S}$ (anlamında ${ displaystyle T}$ uygun şekilde içerir ${ displaystyle S}$ ama daire yok ${ displaystyle U}$ arasında ${ displaystyle S}$ ve ${ displaystyle T}$).

Sınıf ${ displaystyle { mathcal {L}} (M)}$ tüm dairelerin kısmen sipariş küme dahil ederek, oluşturur matroid kafes Tersine, her matroid kafes ${ displaystyle L}$ kümesi üzerinde bir matroid oluşturur ${ displaystyle E}$ nın-nin atomlar aşağıdaki kapatma operatörü altında: bir set için ${ displaystyle S}$ birleştirme ile atomların ${ displaystyle bigvee S}$,

${ displaystyle operatorname {cl} (S) = {x in E mid x leq bigvee S }}$.

Bu matroidin yassı kısımları, kafesin elemanlarıyla bire bir karşılık gelir; kafes elemanına karşılık gelen daire ${ displaystyle y}$ set

${ displaystyle {x in E mid x leq y }}$.

Böylece, bu matroidin düz kısımlarının kafesi doğal olarak izomorfiktir.${ displaystyle L}$.

Hiper düzlemler

Bir rütbe matroidinde ${ displaystyle r}$, bir rütbe dairesi ${ displaystyle r-1}$ denir hiper düzlem. (Hiper düzlemler ayrıca koatomlar veya eş noktalar.) Bunlar maksimum uygun dairelerdir; başka bir deyişle, bir hiper düzlemin aynı zamanda düz olan tek üst kümesi, ${ displaystyle E}$ matroidin tüm unsurlarından. Eşdeğer bir tanım, bir coatom'un bir alt kümesi olmasıdır. E bu kapsamaz M, ancak ona başka herhangi bir öğe eklemek, bir yayılma kümesi oluşturacak şekilde.^[6]

Aile ${ displaystyle { mathcal {H}}}$ Bir matroidin hiper düzlemleri, matroidlerin başka bir aksiyomatizasyonu olarak kabul edilebilecek aşağıdaki özelliklere sahiptir:^[6]

• Farklı kümeler yok ${ displaystyle X}$ ve ${ displaystyle Y}$ içinde ${ displaystyle { mathcal {H}}}$ ile ${ displaystyle X subseteq Y}$. Yani, hiper düzlemler bir Sperner ailesi.
• Her biri için ${ displaystyle x E’de}$ ve farklı ${ mathcal {H}}} içinde { displaystyle Y, Z$ ile ${ displaystyle x notin Y cup Z}$var ${ mathcal {H}}} içinde { displaystyle X$ ile ${ displaystyle (Y cap Z) fincan {x } subseteq X}$.

Grafoitler

Minty (1966) bir grafoid üçlü olarak ${ displaystyle (L, C, D)}$ içinde ${ displaystyle C}$ ve ${ displaystyle D}$ boş olmayan alt kümelerin sınıflarıdır ${ displaystyle L}$ öyle ki

• unsuru yok ${ displaystyle C}$ ("devre" olarak adlandırılır) başka birini içerir,
• unsuru yok ${ displaystyle D}$ ("cocircuit" olarak adlandırılır) başka bir tane içerir,
• ayar yok ${ displaystyle C}$ ve ayarla ${ displaystyle D}$ tam olarak bir öğede kesişir ve
• her ne zaman ${ displaystyle L}$ alt kümelerin ayrık birliği olarak temsil edilir ${ displaystyle R, G, B}$ ile ${ displaystyle G = {g }}$ (bir tekli set), sonra bir ${ displaystyle X C}$ öyle var ki ${ displaystyle g in X subseteq R cup G}$ veya a $D'de { displaystyle Y }$ öyle var ki ${ displaystyle g in Y subseteq B cup G.}$

Bir matroid olduğunu kanıtladı. ${ displaystyle C}$ devrelerin sınıfıdır ve ${ displaystyle D}$ cocircuits sınıfıdır. Tersine, eğer ${ displaystyle C}$ ve ${ displaystyle D}$ bir matroidin devre ve ortak devre sınıflarıdır ${ displaystyle M}$ zemin seti ile ${ displaystyle E}$, sonra ${ displaystyle (E, C, D)}$ bir grafoiddir. Bu nedenle, grafoidler, matroidlerin kendi kendine ikili kriptomorfik aksiyomatizasyonunu sağlar.

Örnekler

Ücretsiz matroid

İzin Vermek ${ displaystyle E}$ sonlu bir küme olun. Tüm alt kümelerinin kümesi ${ displaystyle E}$ matroid tanımını karşılar. Denir ücretsiz matroid bitmiş ${ displaystyle E}$.

Tek tip matroidler

İzin Vermek ${ displaystyle E}$ sonlu bir küme olmak ve ${ displaystyle k}$ a doğal sayı. Bir matroid tanımlanabilir ${ displaystyle E}$ her birini alarak ${ displaystyle k}$-element alt kümesi ${ displaystyle E}$ temel olmak. Bu, tek tip matroid rütbe ${ displaystyle k}$. Sıralamalı tek tip bir matroid ${ displaystyle k}$ Ve birlikte ${ displaystyle n}$ elemanlar gösterilir ${ displaystyle U_ {k, n}}$. Seviye en az 2 olan tüm tek tip matroidler basittir (bkz. § Ek terminoloji ). 2. sıradaki tek tip matroid ${ displaystyle n}$ puan denir ${ displaystyle n}$-nokta çizgisi. Bir matroid, ancak ve ancak birden küçük devresi artı matroidin derecesine sahip değilse tekdüzedir. Tek tip matroidlerin doğrudan toplamlarına bölüm matroidleri.

Tek tip matroid içinde ${ displaystyle U_ {0, n}}$, her öğe bir döngüdür (herhangi bir bağımsız kümeye ait olmayan bir öğe) ve tek tip matroid ${ displaystyle U_ {n, n}}$, her öğe bir coloop'tur (tüm temellere ait bir öğe). Bu iki türdeki matroidlerin doğrudan toplamı, her öğenin bir döngü veya bir coloop olduğu bir bölüm matroididir; buna denir ayrık matroid. Ayrık bir matroidin eşdeğer bir tanımı, zemin setinin her uygun, boş olmayan alt kümesinin olduğu bir matroidtir. ${ displaystyle E}$ bir ayırıcıdır.

Doğrusal cebirden matroidler

Fano matroidi Fano uçağı. Bu GF (2) -doğrusal fakat gerçek doğrusal değil.

Vámos matroid, herhangi bir alan üzerinde doğrusal değil

Matroid teorisi, esas olarak vektör uzaylarında bağımsızlık ve boyut özelliklerinin derinlemesine incelenmesinden gelişmiştir. Bu şekilde tanımlanan matroidleri sunmanın iki yolu vardır:

• Eğer ${ displaystyle E}$ herhangi bir sonlu alt kümesidir vektör alanı ${ displaystyle V}$, sonra bir matroid tanımlayabiliriz ${ displaystyle M}$ açık ${ displaystyle E}$ bağımsız kümeleri alarak ${ displaystyle M}$ olmak Doğrusal bağımsız alt kümeleri ${ displaystyle E}$. Bu matroid için bağımsız ayarlanmış aksiyomların geçerliliği, Steinitz döviz lemma. Eğer ${ displaystyle M}$ bu şekilde tanımlanabilen bir matroid, set diyoruz ${ displaystyle E}$ temsil eder ${ displaystyle M}$. Bu tür matroidlere vektör matroidler. Bu şekilde tanımlanan bir matroidin önemli bir örneği, Fano matroididir. Fano uçağı, bir sonlu geometri yedi nokta (matroidin yedi öğesi) ve yedi çizgi (matroidin uygun önemsiz düz kısımları). Öğeleri, üç boyutlu bir vektör uzayında sıfır olmayan yedi nokta olarak tanımlanabilen doğrusal bir matroidtir. sonlu alan GF (2). Bununla birlikte, Fano matroid için benzer bir temsil sağlamak mümkün değildir. gerçek sayılar GF (2) yerine.
• Bir matris ${ displaystyle A}$ bir giriş ile alan matroid yaratır ${ displaystyle M}$ sütun kümesinde. Matroid içindeki bağımlı sütun kümeleri, vektörler olarak doğrusal olarak bağımlı olanlardır. Bu matroid denir sütun matroid nın-nin ${ displaystyle A}$, ve ${ displaystyle A}$ söylendi temsil etmek ${ displaystyle M}$. Örneğin, Fano matroid bu şekilde 3 × 7 olarak temsil edilebilir. (0,1) -matris. Sütun matroidleri, başka bir isim altındaki vektör matroidleridir, ancak genellikle matris temsilini tercih etmenin nedenleri vardır. (Tek bir teknik fark vardır: bir sütun matroidi aynı vektör olan farklı elemanlara sahip olabilir, ancak yukarıda tanımlandığı gibi bir vektör matroidi olamaz. Bu fark genellikle önemsizdir ve göz ardı edilebilir, ancak ${ displaystyle E}$ olmak çoklu set vektörlerden biri, iki tanımı tam bir uyum içinde getirir.)

Bir vektör matroidine eşdeğer bir matroid, farklı şekilde sunulabilmesine rağmen, temsil edilebilir veya doğrusal. Eğer ${ displaystyle M}$ bir vektör matroidine eşittir alan ${ displaystyle F}$sonra diyoruz ${ displaystyle M}$ dır-dir temsil edilebilir ${ displaystyle F}$; özellikle, ${ displaystyle M}$ dır-dir gerçek temsil edilebilir gerçek sayılar üzerinde gösterilebilirse. Örneğin, bir grafik matroid (aşağıya bakınız) bir grafik olarak sunulsa da, herhangi bir alan üzerinde vektörlerle de gösterilebilir. Matroid teorisindeki temel bir problem, belirli bir alan üzerinde temsil edilebilen matroidleri karakterize etmektir. ${ displaystyle F}$; Rota varsayımı her biri için olası bir karakterizasyonu tanımlar sonlu alan. Şimdiye kadarki ana sonuçlar, ikili matroidler (GF (2) üzerinde gösterilebilenler) nedeniyle Tutte (1950'ler), Reid ve Bixby'den kaynaklanan üçlü matroidlerin (3 element alanı üzerinde gösterilebilir) ve ayrıca Seymour (1970'ler) ve Geelen, Gerards ve Kapoor'a (2000) bağlı dördüncül matroidler (4 element alanında gösterilebilir). Bu oldukça açık bir alan.^{[güncellenmesi mi gerekiyor? ]}

Bir normal matroid olası tüm alanlarda gösterilebilen bir matroid. Vámos matroid herhangi bir alanda gösterilemeyen bir matroidin en basit örneğidir.

Grafik teorisinden matroidler

Matroid teorisi için ikinci bir orijinal kaynak, grafik teorisi.

Her sonlu grafik (veya çoklu grafik ) ${ displaystyle G}$ matroid yaratır ${ displaystyle M (G)}$ aşağıdaki gibi: al ${ displaystyle E}$ tüm kenarların kümesi ${ displaystyle G}$ ve yalnızca ve ancak bir orman; yani, eğer bir basit döngü. Sonra ${ displaystyle M (G)}$ denir döngüsü matroid. Bu şekilde türetilen matroidler grafik matroidler. Her matroid grafik değildir, ancak üç element üzerindeki tüm matroidler grafiktir.^[7] Her grafik matroid normaldir.

Grafiklerdeki diğer matroidler daha sonra keşfedildi:

• iki dairesel matroid Her bağlı alt küme en fazla bir döngü içeriyorsa bağımsız olarak bir dizi kenar çağırarak tanımlanır.
• Yönlendirilmiş veya yönlendirilmemiş herhangi bir grafikte ${ displaystyle G}$ İzin Vermek ${ displaystyle E}$ ve ${ displaystyle F}$ iki ayrı köşe kümesi olabilir. Sette ${ displaystyle E}$, bir alt küme tanımlayın ${ displaystyle U}$ varsa bağımsız olmak |${ displaystyle U}$| köşeden ayrık yollar ${ displaystyle F}$ üstüne ${ displaystyle U}$. Bu bir matroidi tanımlar ${ displaystyle E}$ deniliyor gammoid:^[8] a katı gammoid setin olduğu ${ displaystyle E}$ tam köşe kümesidir ${ displaystyle G}$.^[9]
• İçinde iki parçalı grafik ${ displaystyle G = (U, V, E)}$, elemanların bir tarafta köşeler olduğu bir matroid oluşturabilir ${ displaystyle U}$ iki bölümden oluşur ve bağımsız alt kümeler, eşleşmeler grafiğin. Buna a enine matroid,^[10][11] ve bir gammoidin özel bir durumudur.^[8] Enine matroidler, çift ​​matroidler katı gammoidlere.^[9]
• Grafik matroidler, matroidlere genelleştirilmiştir. imzalı grafikler, grafikler kazanmak, ve önyargılı grafikler. Grafik ${ displaystyle G}$ seçkin bir doğrusal sınıf ile ${ displaystyle B}$ "önyargılı grafik" olarak bilinen döngülerin sayısı ${ displaystyle (G, B)}$, iki matroidi vardır. çerçeve matroid ve kaldırma matroid önyargılı grafiğin. Her döngü seçkin sınıfa aitse, bu matroidler, döngü matroidi ile çakışır. ${ displaystyle G}$. Herhangi bir döngü ayırt edilmezse, çerçeve matroidi, ${ displaystyle G}$. Kenarları işaretlerle etiketlenen işaretli bir grafik ve kenarları bir gruptan yönlendirilebilir şekilde etiketlenen bir grafik olan kazanç grafiği her biri yanlı bir grafiğe yol açar ve bu nedenle çerçeve ve kaldırma matroidlerine sahiptir.
• Laman grafikleri iki boyutun temellerini oluşturur sertlik matroid teorisinde tanımlanan bir matroid yapısal sertlik.
• İzin Vermek ${ displaystyle G}$ bağlantılı bir grafik olun ve ${ displaystyle E}$ kenar seti. İzin Vermek ${ displaystyle I}$ alt kümelerin koleksiyonu olmak ${ displaystyle F}$ nın-nin ${ displaystyle E}$ öyle ki ${ displaystyle G-F}$ hala bağlı. Sonra ${ displaystyle M ^ {*} (G)}$, eleman kümesi ${ displaystyle E}$ Ve birlikte ${ displaystyle I}$ bağımsız kümeler sınıfı olarak, bağ matroid nın-nin ${ displaystyle G}$. Sıralama işlevi ${ displaystyle r (F)}$ ... siklomatik sayı kenar alt kümesinde indüklenen alt grafiğin ${ displaystyle F}$, bu alt grafiğin maksimum ormanının dışındaki kenarların sayısına ve ayrıca içindeki bağımsız döngülerin sayısına eşittir.

Alan uzantılarından matroidler

Matroid teorisinin üçüncü bir orijinal kaynağı alan teorisi.

Bir uzantı bir alan bir matroid ortaya çıkarır. Varsayalım ${ displaystyle F}$ ve ${ displaystyle K}$ alanlardır ${ displaystyle K}$ kapsamak ${ displaystyle F}$. İzin Vermek ${ displaystyle E}$ herhangi bir sonlu alt kümesi olmak ${ displaystyle K}$. Bir alt küme tanımlayın ${ displaystyle S}$ nın-nin ${ displaystyle E}$ olmak cebirsel olarak bağımsız uzantı alanı ${ displaystyle F (S)}$ vardır aşkınlık derecesi eşittir ${ displaystyle | S |}$.^[12]

Bu türden bir matroide eşdeğer olan bir matroid, cebirsel matroid.^[13] Cebirsel matroidleri karakterize etme sorunu son derece zordur; onun hakkında çok az şey biliniyor. Vámos matroid cebirsel olmayan bir matroid örneği sağlar.

Temel yapılar

Eski matroidlerden yeni matroidler yapmanın bazı standart yolları vardır.

Dualite

Eğer M sonlu bir matroid, tanımlayabiliriz dikey veya çift ​​matroid M* aynı temel seti alıp a setini çağırarak temel içinde M* eğer ve ancak tamamlayıcısı bir temel ise M. Bunu doğrulamak zor değil M* bir matroid ve M* dır-dir M.^[14]

İkili, bir matroidi tanımlamanın diğer yolları açısından eşit derecede iyi tanımlanabilir. Örneğin:

• Bir küme bağımsızdır M* ancak ve ancak tamamlayıcısı genişlerse M.
• Bir küme bir devredir M* eğer ve ancak tamamlayıcısı bir coatom ise M.
• Dual'in rank fonksiyonu ${ Displaystyle r ^ {*} (S) = | S | -r (M) + r sol (E setminus S sağ)}$.

Matroid sürümüne göre Kuratowski teoremi, grafik matroidin ikilisi M bir grafik matroidtir, ancak ve ancak M bir matroid düzlemsel grafik. Bu durumda, ikilisi M matroid ikili grafik nın-nin G.^[15] Belirli bir alan üzerinde gösterilebilen bir vektör matroidinin ikilisi F ayrıca temsil edilebilir F. Enine bir matroidin ikilisi katı bir gammoiddir ve bunun tersi de geçerlidir.

Misal

Bir grafiğin döngü matroidi, bağ matroidinin ikili matroididir.

Küçükler

Eğer M element setli bir matroid E, ve S alt kümesidir E, kısıtlama nın-nin M -e S, yazılı M |S, setteki matroid S bağımsız kümeleri bağımsız kümelerdir M İçerdiği S. Devreleri şu devrelerdir: M İçerdiği S ve rank fonksiyonu şudur: M alt kümeleriyle sınırlı S. Doğrusal cebirde, bu, içindeki vektörler tarafından üretilen alt uzay ile sınırlandırmaya karşılık gelir. S. Eşdeğer olarak eğer T = M−S bu şu şekilde adlandırılabilir: silme nın-nin T, yazılı M\T veya M−T. Alt matroidler M tam olarak bir dizi silme işleminin sonucudur: sıra alakasızdır.^[16][17]

Sınırlamanın ikili işlevi daralmadır.^[18] Eğer T alt kümesidir E, kasılma nın-nin M tarafından T, yazılı M/T, temel setteki matroid E - T kimin rank işlevi ${ Displaystyle r '(A) = r (A fincan T) -r (T).}$^[19] Doğrusal cebirde, bu, bölüm uzayına, içindeki vektörler tarafından üretilen doğrusal uzay ile bakmaya karşılık gelir. Tvektörlerin görüntüleri ile birlikte E - T.

Bir matroid N -dan elde edilir M bir dizi kısıtlama ve daraltma işlemine göre minör nın-nin M.^[17][20] Diyoruz M içerir N küçük olarak. Birçok önemli matroid ailesi şu özelliklere sahip olabilir: minör-minimal aileye ait olmayan matroidler; bunlara denir yasak veya küçükler hariç.^[21]

Toplamlar ve birlikler

İzin Vermek M temel unsurları olan bir matroid olmak Eve izin ver N temel bir sette başka bir matroid olmak F.The doğrudan toplam matroidlerin M ve N temel seti olan matroid ayrık birlik nın-nin E ve Fve bağımsız kümeleri, bağımsız bir kümenin ayrık birlikleri olan M bağımsız bir dizi ile N.

Birlik nın-nin M ve N temel seti birliği (ayrık birleşimi değil) olan matroid E ve Fve bağımsız kümeleri, bağımsız bir kümenin birleşimi olan alt kümelerdir. M ve biri N. Genellikle "sendika" terimi, E = F, ancak bu varsayım gerekli değildir. Eğer E ve F ayrık, sendika doğrudan toplamıdır.

Ek terminoloji

İzin Vermek M temel unsurları olan bir matroid olmak E.

• E denilebilir zemin seti nın-nin M. Öğeleri, puan nın-nin M.
• Altkümesi E aralıklar M eğer kapanışı ise E. Bir set söyleniyor açıklık kapalı bir set K eğer kapanışı ise K.
• çevresi Bir matroid, en küçük devresinin veya bağımlı kümesinin boyutudur.
• Tek elemanlı bir devre oluşturan bir eleman M denir döngü. Aynı şekilde, bir eleman, temele ait değilse bir döngüdür.^[7][22]
• Hiçbir devreye ait olmayan bir elemana a Colop veya isthmus. Aynı şekilde, bir öğe, her temele aitse bir coloop'dur. Döngü ve ortak döngüler karşılıklı olarak ikilidir.^[22]
• İki öğeli bir set {f, g} bir devresidir M, sonra f ve g vardır paralel içinde M.^[7]
• Bir matroid denir basit 1 veya 2 elementten oluşan devresi yoksa. Yani, döngüleri ve paralel öğeleri yoktur. Dönem kombinatoryal geometri ayrıca kullanılır.^[7] Başka bir matroidden elde edilen basit bir matroid M 2 elemanlı devre kalmayana kadar tüm döngüleri silerek ve her 2 elemanlı devreden bir eleman silerek, basitleştirme nın-nin M.^[23] Bir matroid ortak basit çift ​​matroidi basitse.^[24]
• Bir devreler birliği bazen bir döngü nın-nin M. Bu nedenle bir döngü, çift matroidin bir düzlüğünün tamamlayıcısıdır. (Bu kullanım, grafik teorisindeki "döngü" nin ortak anlamı ile çelişir.)
• Bir ayırıcı nın-nin M bir alt kümedir S nın-nin E öyle ki ${ Displaystyle r (S) + r (E-S) = r (M)}$. Bir uygun veya önemsiz olmayan ayırıcı ne bir ayırıcıdır E ne de boş küme.^[25] Bir indirgenemez ayırıcı boş olmayan başka ayırıcı içermeyen bir ayırıcıdır. İndirgenemez ayırıcılar zemin setini böler E.
• Boş olmayan iki matroidin doğrudan toplamı olarak yazılamayan veya eşdeğer olarak uygun ayırıcıları olmayan bir matroid denir bağlı veya indirgenemez. Bir matroid, ancak ve ancak ikilisi bağlıysa bağlanır.^[26]
• Azami indirgenemez bir alt matroid M denir bileşen nın-nin M. Bir bileşen, M indirgenemez bir ayırıcıya ve tersine, kısıtlama M indirgenemez bir ayırıcı için bir bileşendir. Ayırıcı, bileşenlerin birleşimidir.^[25]
• Bir matroid M denir çerçeve matroid eğer o veya onu içeren bir matroid, tüm noktalarının M temel eleman çiftlerini birleştiren satırlarda bulunur.^[27]
• Bir matroid a denir kaldırım matroid eğer tüm devrelerinin boyutu en azından kendi seviyesine eşitse.^[28]
• matroid politop ${ displaystyle P_ {M}}$ ... dışbükey örtü of gösterge vektörleri temellerinin ${ displaystyle M}$.

Algoritmalar

Açgözlü algoritma

Bir ağırlıklı matroid öğelerinden negatif olmayana kadar bir işlevle birlikte bir matroid gerçek sayılar. Bir eleman alt kümesinin ağırlığı, alt kümedeki elemanların ağırlıklarının toplamı olarak tanımlanır. Açgözlü algoritma boş kümeden başlayarak ve her seferinde bir öğeyi tekrar tekrar ekleyerek, her adımda eklenmesi artırılmış öğenin bağımsızlığını koruyacak öğeler arasından bir maksimum ağırlık öğesi seçerek matroidin maksimum ağırlık temelini bulmak için kullanılabilir. Ayarlamak.^[29] Bu algoritmanın, matroide bir aracılığıyla erişebildiği sürece, matroid tanımının ayrıntıları hakkında hiçbir şey bilmesine gerek yoktur. bağımsızlık kahini, bir kümenin bağımsız olup olmadığını test etmek için bir alt yordam.

Bu optimizasyon algoritması, matroidleri karakterize etmek için kullanılabilir: eğer bir aile F Alt kümeler altında kapatılan kümeler, kümelerin ağırlığı ne olursa olsun, açgözlü algoritmanın ailede bir maksimum ağırlık kümesi bulması özelliğine sahiptir. F bir matroidin bağımsız kümelerinin ailesi olmalıdır.^[30]

Matroid kavramı, açgözlü bir algoritmanın en uygun çözümleri sunduğu diğer set türlerine izin verecek şekilde genelleştirilmiştir; görmek açgözlü ve matroid yerleştirme daha fazla bilgi için.

Matroid bölümleme

matroid bölümleme problem, bir matroidin elemanlarını olabildiğince az bağımsız kümeye bölmektir ve matroid paketleme problemi, olabildiğince çok sayıda ayrık yayılma kümesi bulmaktır. Her ikisi de polinom zamanında çözülebilir ve sıralamayı hesaplama veya bir matroid toplamında bağımsız bir küme bulma problemine genelleştirilebilir.

Matroid kavşağı

kavşak iki veya daha fazla matroidin, matroidlerin her birinde aynı anda bağımsız olan kümeler ailesidir. İki matroidin kesişme noktasında en büyük seti veya maksimum ağırlıklı seti bulma problemi şu şekilde bulunabilir: polinom zamanı ve diğer birçok önemli kombinatoryal optimizasyon problemine çözüm sağlar. Örneğin, maksimum eşleşme içinde iki parçalı grafikler ikisini kesişme sorunu olarak ifade edilebilir bölüm matroidleri. Bununla birlikte, üç veya daha fazla matroidin kesişimindeki en büyük seti bulmak NP tamamlandı.

Matroid yazılımı

Matroidlerle hesaplamalar için iki bağımsız sistem Kingan'ın Oid ve Hlineny'nin Macek. Her ikisi de açık kaynaklı paketlerdir. "Oid" matroidlerle deney yapmak için etkileşimli, genişletilebilir bir yazılım sistemidir. "Macek", temsil edilebilir matroidlerle makul derecede verimli kombinatoryal hesaplamalar için araçlar ve rutinler içeren özel bir yazılım sistemidir.

Her iki açık kaynak matematik yazılım sistemi ADAÇAYI ve Macaulay2 matroid paketleri içerir.

Polinom değişmezler

Sonlu bir matroid ile ilişkili iki özellikle önemli polinom vardır M yer setinde E. Her biri bir matroid değişmezBu, izomorfik matroidlerin aynı polinoma sahip olduğu anlamına gelir.

Karakteristik polinom

karakteristik polinom nın-nin M (buna bazen denir kromatik polinom,^[31] renklendirmeleri saymasa da) olarak tanımlanır

${ displaystyle p_ {M} ( lambda): = toplam _ {S subseteq E} (- 1) ^ {| S |} lambda ^ {r (M) -r (S)},}$

veya eşdeğer olarak (boş küme kapalı olduğu sürece M) gibi

${ displaystyle p_ {M} ( lambda): = toplamı _ {A} mu ( boş küme, A) lambda ^ {r (M) -r (A)} ,}$

μ, Möbius işlevi of geometrik kafes matroid ve toplam matroidin tüm düz kısımları A üzerinden alınır.^[32]

Ne zaman M döngü matroididir M(G) bir grafiğin Gkarakteristik polinom, küçük bir dönüşümdür. kromatik polinom by ile verilir_G (λ) = λ^cp_M(G) (λ), nerede c bağlı bileşenlerin sayısı G.

Ne zaman M tahvil matroidi M*(G) bir grafiğin Gkarakteristik polinom eşittir akış polinomu nın-nin G.

Ne zaman M matroid M(Bir) bir aranjman Bir doğrusal hiper düzlemlerin Rⁿ (veya Fⁿ nerede F herhangi bir alandır), düzenlemenin karakteristik polinomu ile verilir p_Bir (λ) = λ^n−r(M)p_M(Bir) (λ).

Beta değişmez

beta değişmez bir matroidin tanıttığı Crapo (1967), karakteristik polinom olarak ifade edilebilir p türevin bir değerlendirmesi olarak^[33]

${ displaystyle beta (M) = (- 1) ^ {r (M) -1} p_ {M} '(1) }$

veya doğrudan^[34]

${ displaystyle beta (M) = (- 1) ^ {r (M)} toplamı _ {X subseteq E} (- 1) ^ {| X |} r (X) .}$

Beta değişmezi negatif değildir ve ancak ve ancak M bağlantısı kesilmiş veya boş veya bir döngü. Aksi takdirde, sadece dairelerin kafesine bağlıdır. M. Eğer M döngü ve coloop içermez, sonra β (M) = β (M^∗).^[34]

Tutte polinomu

Tutte polinomu bir matroidin T_M (x,y), karakteristik polinomu iki değişkene geneller. Bu ona daha kombinatoryal yorumlar verir ve aynı zamanda ona dualite özelliğini verir.

${ displaystyle T_ {M ^ {*}} (x, y) = T_ {M} (y, x),}$

bu, özellikleri arasında bir dizi ikilem anlamına gelir M ve özellikleri M *. Tutte polinomunun bir tanımı şudur:

${ displaystyle T_ {M} (x, y) = toplamı _ {S subseteq E} (x-1) ^ {r (M) -r (S)} (y-1) ^ {| S | - r (S)}.}$

Bu, Tutte polinomunu bir değerlendirme olarak ifade eder. corank-nullity veya sıra üreten polinom,^[35]

${ displaystyle R_ {M} (u, v) = toplam _ {S subseteq E} u ^ {r (M) -r (S)} v ^ {| S | -r (S)}.}$

Bu tanımdan, karakteristik polinomun basit bir faktöre kadar, bir değerlendirme olduğunu görmek kolaydır. T_M, özellikle,

${ displaystyle p_ {M} ( lambda) = (- 1) ^ {r (M)} T_ {M} (1- lambda, 0).}$

Diğer bir tanım, iç ve dış faaliyetler açısından ve temellerin toplamıdır ve bu gerçeği yansıtır. T(1,1) baz sayısıdır.^[36] Daha az alt kümeyi toplayan ancak daha karmaşık terimleri olan bu, Tutte'nin orijinal tanımıydı.

Silme ve daraltma yoluyla özyineleme açısından başka bir tanım daha vardır.^[37] Silme-daraltma kimliği

${ displaystyle F (M) = F (M-e) + F (M / e)}$ ne zaman ${ displaystyle e}$ ne bir döngü ne de bir coloop.

Bu özyinelemeyi ve çarpımsal koşulu karşılayan bir matroid değişmezi (yani, izomorfik matroidler üzerinde aynı değeri alan bir fonksiyon)

${ displaystyle F (M oplus M ') = F (M) F (M')}$

olduğu söyleniyor Tutte-Grothendieck değişmez.^[35] Tutte polinomu, bu türden en genel değişmezdir; yani Tutte polinomu bir Tutte-Grothendieck değişmezidir ve bu tür her değişmez Tutte polinomunun bir değerlendirmesidir.^[31]

Tutte polinomu T_G Bir grafiğin Tutte polinomu T_M(G) döngü matroidinin.

Sonsuz matroidler

Sonsuz matroid teorisi, sonlu matroidlerden çok daha karmaşıktır ve kendi başına bir konu oluşturur. Uzun zamandır, zorluklardan biri, hiçbiri sonlu matroid teorisinin tüm önemli yönlerini ele almayan birçok makul ve kullanışlı tanımın bulunmasıydı. Örneğin, sonsuz matroidler kavramında temellere, devrelere ve dualiteye sahip olmak zor görünüyordu.

Sonsuz bir matroidin en basit tanımı, sonlu sıra; yani rütbesi E sonludur. Bu teori, sonlu sıralı sonsuz bir matroidin dualinin sonlu sıraya sahip olmaması nedeniyle dualitenin başarısızlığı dışında sonlu matroidlerinkine benzer. Sonlu sıralı matroidler, sonlu boyutlu vektör uzaylarının herhangi bir alt kümesini ve alan uzantıları sonlu aşkınlık derecesi.

Bir sonraki en basit sonsuz genelleme, sonlu matroidlerdir. Bir matroid finiter özelliği varsa

${ displaystyle x , cl (Y) Leftrightarrow ( var Y ' subseteq Y) Y' { text {sonludur ve}} x , cl (Y ') içinde.}$

Eşdeğer olarak, her bağımlı küme sonlu bir bağımlı küme içerir.Örnekler, sonsuz boyutlu keyfi alt kümelerinin doğrusal bağımlılığıdır. vektör uzayları (ancak olduğu gibi sonsuz bağımlılıklar değil Hilbert ve Banach uzayları ) ve muhtemelen sonsuz aşkınlık derecesindeki alan uzantılarının keyfi alt kümelerindeki cebirsel bağımlılık. Yine, sonlu matroid sınıfı kendiliğinden ikili değildir, çünkü sonlu bir matroidin ikilisi sonlu değildir. model teorisi bir dalı matematiksel mantık güçlü bağları olan cebir.

1960'ların sonlarında matroid teorisyenleri, sonlu matroidlerin farklı yönlerini paylaşan ve dualitelerini genelleştiren daha genel bir fikir istediler. Bu zorluğa yanıt olarak birçok sonsuz matroid kavramı tanımlandı, ancak soru açık kaldı. D.A. tarafından incelenen yaklaşımlardan biri. Higgs şu şekilde tanındı: B-matroidler 1960'larda ve 1970'lerde Higgs, Oxley ve diğerleri tarafından incelendi. Bruhn, Diestel ve Kriesell ve ark. Tarafından yapılan son sonuca göre. (2013 ), sorunu çözer: Aynı fikre bağımsız olarak vararak, beş eşdeğer aksiyom sistemi sağladılar - bağımsızlık, temeller, devreler, kapanış ve derece açısından. B-matroidlerin dualitesi, sonsuz grafiklerde gözlemlenebilen dualiteleri genelleştirir.

Bağımsızlık aksiyomları aşağıdaki gibidir:

1. Boş küme bağımsızdır.
2. Bağımsız bir kümenin her alt kümesi bağımsızdır.
3. Her biri için maksimal olmayan (küme dahil etme altında) bağımsız küme ben ve maksimum bağımsız küme J, var ${ displaystyle x in J setminus I}$ öyle ki ${ displaystyle I fincan {x }}$ bağımsızdır.
4. Her alt küme için X temel alan, her bağımsız alt küme ben nın-nin X maksimum bağımsız bir alt kümeye genişletilebilir X.

Bu aksiyomlarla, her matroidin bir ikilisi vardır.

Tarih

Matroid teorisi, Hassler Whitney  (1935 ). Ayrıca bağımsız olarak keşfedildi Takeo Nakasawa, yıllarca işi unutulan (Nishimura ve Kuroda 2009 ).

Whitney ufuk açıcı makalesinde bağımsızlık için iki aksiyom sağladı ve bu aksiyomlara bağlı herhangi bir yapıyı "matroid" olarak tanımladı. (Muhtemelen ima edilmiş olsa da, bağımsız olması için en az bir alt kümeyi gerektiren bir aksiyom içermedi.) temel gözlem, bu aksiyomların hem grafikler hem de matrisler için ortak olan bir "bağımsızlık" soyutlaması sağlamasıydı. Bu nedenle, matroid teorisinde kullanılan terimlerin çoğu, aşağıdaki benzer kavramların terimlerine benzemektedir. lineer Cebir veya grafik teorisi.

Whitney'in matroidler hakkında yazdığı ilk yazının hemen ardından, önemli bir makale yazılmıştır. Saunders Mac Lane  (1936 ) matroidlerin ilişkisi üzerine projektif geometri. Bir yıl sonra, B. L. van der Waerden  (1937 ) Modern Cebir üzerine klasik ders kitabında cebirsel ve doğrusal bağımlılık arasındaki benzerlikleri kaydetti.

1940'larda Richard Rado "bağımsızlık sistemleri" adı altında daha fazla teori geliştirdi. enine teori, konu için adının hala bazen kullanıldığı yerde.

1950 lerde W. T. Tutte matroid teorisinin en önde gelen figürü oldu, yıllarca koruduğu bir pozisyon oldu. Katkıları, karakterizasyonu da dahil olmak üzere çok fazlaydı. ikili, düzenli, ve grafik matroids sıralama küçükler hariç; düzenli matroid temsil edilebilirlik teoremi; zincir gruplarının teorisi ve matroidleri; ve sonuçlarını kanıtlamak için kullandığı araçlar, "Yol teoremi" ve "Tutte homotopi teoremi "(bkz. ör. Tutte 1965 ), o kadar karmaşık ki, daha sonraki teorisyenler bunları ispatlarda kullanma zorunluluğunu ortadan kaldırmak için büyük zahmete girdiler. (Güzel bir örnek A. M. H. Gerards kısa kanıt (1989 ) Tutte'nin normal matroidlerin karakterizasyonu.)

Henry Crapo  (1969 ) ve Thomas Brylawski  (1972 ) matroidlere genelleştirilmiştir Tutte'nin "dikromatı", şimdi şu adıyla bilinen bir grafik polinomu Tutte polinomu (Crapo tarafından adlandırılmıştır). Çalışmalarını son zamanlarda (özellikle 2000'lerde), bir grafiğin Tutte polinomundaki kadar olmasa da bir dizi kağıt takip etti.

1976'da Dominic Welsh matroid teorisi üzerine ilk kapsamlı kitabı yayınladı.

Paul Seymour düzenli matroidler için ayrışma teoremi (1980 ) 1970'lerin sonlarının ve 1980'lerin en önemli ve etkili çalışmasıydı. Kahn ve Kung (1982), projektif geometrilerin neden gösterdiğini ve Dowling geometrileri matroid teorisinde çok önemli bir rol oynar.

Bu zamana kadar birçok önemli katkıda bulunanlar vardı, ancak bunlardan bahsetmeyi ihmal etmemek Geoff Whittle Tutte'nin rasyoneller üzerinden temsil edilebilen ikili matroidlerin karakterizasyonunun üçlü matroidlere uzantısı (Whittle 1995 ), belki de 1990'ların en büyük tek katkısı. Cari dönemde (yaklaşık 2000'den beri) Matroid Küçükler Projesi Jim Geelen, Gerards, Whittle ve diğerleri, sonlu bir alan üzerinde temsil edilebilen matroidler için Robertson – Seymour Graph Minors Projesinin başarısını çoğaltmaya çalışan diğerleri (bkz. Robertson-Seymour teoremi ), matroidlerin yapı teorisinde önemli ilerlemeler sağladı. Diğerleri de matroid teorisinin (21. yüzyılın birinci ve ikinci on yıllarında) gelişen kısmına katkıda bulundu.

Araştırmacılar

Matroid çalışmalarına öncülük eden matematikçiler arasında Takeo Nakasawa,^[38] Saunders Mac Lane, Richard Rado, W. T. Tutte, B. L. van der Waerden, ve Hassler Whitney Diğer büyük katkıda bulunanlar arasında Jack Edmonds, Jim Geelen, Eugene Lawler, László Lovász, Gian-Carlo Rota, P. D. Seymour, ve Dominic Welsh.

Ayrıca bakınız

• Antimatroid
• Coxeter matroid
• Odaklı matroid
• Pregeometri (model teorisi)
• Polimatroid
• Greedoid

Notlar

Referanslar

• Bruhn, Henning; Diestel, Reinhard; Kriesell, Matthias; Pendavingh, Rudi; Wollan, Paul (2013), "Axioms for infinite matroids", Matematikteki Gelişmeler, 239: 18–46, arXiv:1003.3919, doi:10.1016/j.aim.2013.01.011, BAY  3045140.
• Bryant, Victor; Mükemmel, Hazel (1980), Kombinatorikte Bağımsızlık Teorisi, London and New York: Chapman and Hall, ISBN  978-0-412-22430-0.
• Brylawski, Thomas H. (1972), "A decomposition for combinatorial geometries", Amerikan Matematik Derneği İşlemleri, 171: 235–282, doi:10.2307/1996381, JSTOR  1996381.
• Crapo, Henry H. (1969), "The Tutte polynomial", Aequationes Mathematicae, 3 (3): 211–229, doi:10.1007/BF01817442.
• Crapo, Henry H.; Rota, Gian-Carlo (1970), On the Foundations of Combinatorial Theory: Combinatorial Geometries, Cambridge, Mass.: M.I.T. Basın, ISBN  978-0-262-53016-3, BAY  0290980.
• Geelen, Jim; Gerards, A. M. H .; Whittle, Geoff (2007), "Towards a matroid-minor structure theory", in Grimmett, Geoffrey; et al. (eds.), Kombinasyon, Karmaşıklık ve Şans: Dominic Welsh'e Bir Övgü, Oxford Lecture Series in Mathematics and its Applications, 34, Oxford: Oxford University Press, pp. 72–82.
• Gerards, A. M. H. (1989), "Tutte'nin tamamen tek modlu matrislerin karakterizasyonunun kısa bir kanıtı", Doğrusal Cebir ve Uygulamaları, 114/115: 207–212, doi:10.1016/0024-3795(89)90461-8.
• Kahn, Jeff; Kung, Joseph P. S. (1982), "Varieties of combinatorial geometries", Amerikan Matematik Derneği İşlemleri, 271 (2): 485–499, doi:10.2307/1998894, JSTOR  1998894.
• Kingan, Robert; Kingan, Sandra (2005), "A software system for matroids", Graphs and Discovery, DIMACS Series in Discrete Mathematics and Theoretical Computer Science, pp. 287–296.
• Kung, Joseph P. S., ed. (1986), A Source Book in Matroid Theory Boston: Birkhäuser, doi:10.1007/978-1-4684-9199-9, ISBN  978-0-8176-3173-4, BAY  0890330.
• Mac Lane, Saunders (1936), "Some interpretations of abstract linear dependence in terms of projective geometry", Amerikan Matematik Dergisi, 58 (1): 236–240, doi:10.2307/2371070, JSTOR  2371070.
• Minty, George J. (1966), "On the axiomatic foundations of the theories of directed linear graphs, electrical networks and network-programming", Matematik ve Mekanik Dergisi, 15: 485–520, BAY  0188102.
• Nishimura, Hirokazu; Kuroda, Susumu, eds. (2009), A lost mathematician, Takeo Nakasawa. The forgotten father of matroid theory, Basel: Birkhäuser Verlag, doi:10.1007/978-3-7643-8573-6, ISBN  978-3-7643-8572-9, BAY  2516551, Zbl  1163.01001.
• Oxley, James (1992), Matroid Teorisi, Oxford: Oxford University Press, ISBN  978-0-19-853563-8, BAY  1207587, Zbl  0784.05002.
• Recski, András (1989), Matroid Theory and its Applications in Electric Network Theory and in StaticsAlgoritmalar ve Kombinatorikler, 6, Berlin and Budapest: Springer-Verlag and Akademiai Kiado, doi:10.1007/978-3-662-22143-3, ISBN  978-3-540-15285-9, BAY  1027839.
• Sapozhenko, A.A. (2001) [1994], "Matroid", Matematik Ansiklopedisi, EMS Basın
• Seymour, Paul D. (1980), "Düzenli matroidlerin ayrıştırılması", Kombinatoryal Teori Dergisi, B Serisi, 28 (3): 305–359, doi:10.1016/0095-8956(80)90075-1, hdl:10338.dmlcz / 101946, Zbl  0443.05027.
• Truemper Klaus (1992), Matroid Ayrıştırması, Boston: Academic Press, ISBN  978-0-12-701225-4, BAY  1170126.
• Tutte, W. T. (1959), "Matroids and graphs", Amerikan Matematik Derneği İşlemleri, 90 (3): 527–552, doi:10.2307/1993185, JSTOR  1993185, BAY  0101527.
• Tutte, W. T. (1965), "Lectures on matroids", Ulusal Standartlar Bürosu Araştırma Dergisi Bölüm B, 69: 1–47.
• Tutte, W.T. (1971), Introduction to the theory of matroids, Modern Analytic and Computational Methods in Science and Mathematics, 37, New York: American Elsevier Publishing Company, Zbl  0231.05027.
• Vámos, Peter (1978), "The missing axiom of matroid theory is lost forever", Journal of the London Mathematical Society, 18 (3): 403–408, doi:10.1112 / jlms / s2-18.3.403.
• van der Waerden, B. L. (1937), Moderne Cebir.
• Welsh, D. J. A. (1976), Matroid Teorisi, L.M.S. Monographs, 8Akademik Basın, ISBN  978-0-12-744050-7, Zbl  0343.05002.
• White, Neil, ed. (1986), Matroidlerin Teorisi, Matematik Ansiklopedisi ve Uygulamaları, 26, Cambridge: Cambridge University Press, ISBN  978-0-521-30937-0, Zbl  0579.00001.
• White, Neil, ed. (1987), Combinatorial geometries, Matematik Ansiklopedisi ve Uygulamaları, 29, Cambridge: Cambridge University Press, ISBN  978-0-521-33339-9, Zbl  0626.00007
• White, Neil, ed. (1992), Matroid Applications, Matematik Ansiklopedisi ve Uygulamaları, 40, Cambridge: Cambridge University Press, ISBN  978-0-521-38165-9, Zbl  0742.00052.
• Whitney, Hassler (1935), "Doğrusal bağımlılığın soyut özellikleri üzerine", Amerikan Matematik Dergisi, 57 (3): 509–533, doi:10.2307/2371182, hdl:10338.dmlcz / 100694, JSTOR  2371182, BAY  1507091. Yeniden basıldı Kung (1986), s. 55–79.
• Whittle, Geoff (1995), "A characterization of the matroids representable over GF(3) and the rationals" (PDF), Kombinatoryal Teori Dergisi, B Serisi, 65 (2): 222–261, doi:10.1006/jctb.1995.1052^{[kalıcı ölü bağlantı ]}.

Dış bağlantılar

• "Matroid", Matematik Ansiklopedisi, EMS Basın, 2001 [1994]
• Kingan, Sandra : Matroid teorisi. A large bibliography of matroid papers, matroid software, and links.
• Locke, S. C. : Greedy Algorithms.
• Pagano, Steven R. : Matroids and Signed Graphs.
• Mark Hubenthal: A Brief Look At Matroids (PDF ) (contain proofs for statements of this article)
• James Oxley : What is a matroid? (PDF)
• Neil White : Matroid Applications