Enine (kombinatorikler) - Transversal (combinatorics)

İçinde matematik, Özellikle de kombinatorik verilen set ailesi, burada koleksiyon deniyor C, bir enine (ayrıca a enine kesit^[1][2][3]), koleksiyonun her üyesinden tam olarak bir öğe içeren bir kümedir. Koleksiyonun kümeleri karşılıklı olarak ayrık olduğunda, çaprazın her bir öğesi tam olarak bir üyesine karşılık gelir C (üyesi olduğu set). Orijinal setler ayrık değilse, bir enine tanım için iki olasılık vardır:

• Bir varyasyon, bir birebir örten f enine C öyle ki x bir unsurdur f(x) her biri için x enine olarak. Bu durumda, enine aynı zamanda bir farklı temsilciler sistemi (SDR).^[4]:29
• Daha az yaygın olarak kullanılan diğeri, enine elemanlar ile setler arasında bire bir ilişki gerektirmez. C. Bu durumda, temsilciler sistemi mutlaka farklı değildir.^{[5]:692[6]:322}

İçinde bilgisayar Bilimi, enine işlemlerin hesaplanması, girdi ile çeşitli uygulama alanlarında yararlıdır set ailesi genellikle bir hiper grafik.

Varlık ve sayı

SDR çalışmasındaki temel bir soru, bir SDR'nin var olup olmadığıdır. Hall'un evlilik teoremi Bazıları muhtemelen üst üste binen sonlu bir toplama kümelerinin bir enine olması için gerekli ve yeterli koşulları sağlar. Koşul, her tam sayı için k, her koleksiyonu k setler en azından ortak özellik içermelidir k farklı unsurlar.^[4]:29

Tarafından aşağıdaki ayrıntılandırma H. J. Ryser bu tür SDR'lerin sayısı konusunda daha düşük sınırlar verir.^[7]:48

Teoremi. İzin Vermek S₁, S₂, ..., S_m böyle bir set koleksiyonu olun ${ displaystyle S_ {i_ {1}} cup S_ {i_ {2}} cup dots cup S_ {i_ {k}}}$ en azından içerir k için öğeler k = 1,2,...,m ve herkes için k-combinations {${ displaystyle i_ {1}, i_ {2}, ldots, i_ {k}}$1, 2, ..., tam sayılarının} kadarım ve bu kümelerin her birinin en az t elementler. Eğer t ≤ m en azından koleksiyonda t ! SDR'ler ve eğer t > m en azından koleksiyonda t ! / (t - m)! SDR'ler.

Eşleştirme ve örtme ile ilişkisi

Biri inşa edebilir iki parçalı grafik bir taraftaki köşelerin kümeler, diğer taraftaki köşelerin elemanlar olduğu ve kenarların bir seti içerdiği elemanlara bağladığı. Daha sonra, enine bir eşittir a mükemmel eşleşme bu grafikte.

Biri inşa edebilir hiper grafik köşelerin öğeler olduğu ve hiper kenarların kümeler olduğu. Daha sonra, enine bir eşittir a köşe kapağı bir hipergrafta.

Örnekler

İçinde grup teorisi verilen alt grup H bir grubun G, bir sağ (sırasıyla sol) enine bir Ayarlamak her sağdan tam olarak bir öğe içeren (sırasıyla sol) coset nın-nin H. Bu durumda, "kümeler" (kosetler) karşılıklı olarak ayrıktır, yani kosetler bir bölüm Grubun.

Önceki örneğin belirli bir durumu olarak, grupların doğrudan çarpımı ${ displaystyle G = H times K}$, sonra H kosetlerinin enine K.

Genel olarak, herhangi birinden beri denklik ilişkisi rastgele bir sette, her birinden herhangi bir temsilci seçerek bir bölüme yol açar. denklik sınıfı bir enine sonuçlanır.

Bölüm tabanlı çaprazlamanın başka bir örneği, kişi olarak bilinen eşdeğerlik ilişkisi düşünüldüğünde ortaya çıkar. (set-teorik) bir fonksiyonun çekirdeği, bir işlev için tanımlanmıştır ${ displaystyle f}$ ile alan adı X etki alanının bölümü olarak ${ displaystyle operatorname {ker} f: = sol {, sol {, y X'te orta f (x) = f (y) , sağ } X'de orta x ,sağ}}$. etki alanını hangi bölümler f denklik sınıflarına, öyle ki bir sınıf haritasındaki tüm öğeler aracılığıyla f aynı değere. Eğer f enjekte edici, sadece bir çapraz ${ displaystyle operatorname {ker} f}$. Zorunlu olmayan bir amaç için f, bir enine düzeltmek T nın-nin ${ displaystyle operatorname {ker} f}$ arasında bire bir yazışmaya neden olur T ve görüntü nın-nin f, bundan böyle ${ displaystyle operatorname {Im} f}$. Sonuç olarak, bir işlev ${ displaystyle g: ( operatöradı {Im} f) - T}$ herkes için z içinde ${ displaystyle operatöradı {Im} f, g (z) = x}$ nerede x içindeki benzersiz unsur T öyle ki ${ displaystyle f (x) = z}$; dahası, g genişletilebilir (benzersiz bir şekilde olması gerekmez) böylece bütün olarak tanımlanabilir ortak alan nın-nin f için keyfi değerler seçerek g (z) ne zaman z resminin dışında f. Bunu doğrulamak için basit bir hesaplamadır. g bu şekilde tanımlanan özelliği vardır ${ displaystyle f circ g circ f = f}$, bu kanıtıdır (etki alanı ve ortak etki alanı f aynı settir) tam dönüşüm yarı grubu bir normal yarı grup. ${ displaystyle g}$ (benzersiz olması gerekmez) gibi davranır yarı-ters için f; yarı grup teorisinde buna basitçe ters denir. Bununla birlikte, keyfi bir g yukarıda belirtilen özellik ile "ikili" denklem ${ displaystyle g circ f circ g = g}$ tutmayabilir. Ancak şunu ifade edersek ${ displaystyle h = g circ f circ g}$, sonra f yarı tersi hyani ${ displaystyle h circ f circ h = h}$.

Ortak Çaprazlar

Bir ortak enine koleksiyonların Bir ve B (nerede ${ displaystyle | A | = | B | = n}$) her ikisinin de enine olan bir kümedir Bir ve B. Koleksiyonlar Bir ve B ortak bir enine dönüş varsa ve ancak herkes için ${ displaystyle I, J altküme {1, ..., n }}$,

${ displaystyle | ( bigcup _ {i I} A_ {i}) cap ( bigcup _ {j J} B_ {j}) | geq | I | + | J | -n}$^[8]

Genellemeler

Bir kısmi enine koleksiyonun her üyesinden en fazla bir öğe içeren bir kümedir veya (kavramın daha katı biçiminde) kümeden enjeksiyonla bir kümedir. C. Sonlu bir koleksiyonun çaprazları C Sonlu kümelerin, bir matroid, enine matroid nın-nin C. Enine matroidin bağımsız kümeleri, kısmi enine kesitlerdir. C.^[9]

Bir bağımsız enine ' (ayrıca a gökkuşağı bağımsız küme veya bağımsız temsilciler sistemi) aynı zamanda bir enine olan bağımsız küme belirli bir grafiğin. Mecazi terimlerdeki farkı açıklamak için, aşağıdaki özelliklere sahip bir fakülte düşünün: m fakülte dekanın bir komite kurmak istediği bölümler m üye, bölüm başına bir üye. Böyle bir komite, çaprazdır. Ama şimdi, bazı öğretim üyelerinin birbirinden hoşlanmadığını ve komitede birlikte oturmayı kabul etmediklerini varsayalım. Bu durumda, komite, alttaki grafiğin "hoşlanmama" ilişkilerini tanımladığı bağımsız bir çaprazlama olmalıdır.

Çapraz kavramının başka bir genellemesi, her bir üye ile boş olmayan bir kesişim noktası olan bir küme olacaktır. C. İkincisine bir örnek bir Bernstein seti, her bir kümeyle boş olmayan bir kesişimi olan bir küme olarak tanımlanır C, ancak hiçbir set içermez C, nerede C hepsinin koleksiyonudur mükemmel setler topolojik Polonya alanı. Başka bir örnek olarak C a'nın tüm satırlarından oluşur projektif düzlem, sonra bir engelleme seti bu düzlemde, her çizgiyle kesişen, ancak çizgi içermeyen bir noktalar kümesidir.

Kategori teorisi

Dilinde kategori teorisi, bir enine karşılıklı olarak ayrık kümelerden oluşan bir koleksiyonun Bölüm of bölüm haritası koleksiyon tarafından tetiklenir.

Hesaplama karmaşıklığı

hesaplama karmaşıklığı bir girdinin tüm çaprazlarını hesaplama set ailesi özellikle çerçevesinde çalışılmıştır numaralandırma algoritmaları.

Ayrıca bakınız

• Seçim aksiyomu
• Kalıcı

Referanslar

daha fazla okuma

• Lawler, E.L. Kombinatoryal Optimizasyon: Ağlar ve Matroidler. 1976.
• Mirsky, Leon (1971). Çaprazlama Teorisi: Kombinatoryal matematiğin bazı yönlerinin açıklaması. Akademik Basın. ISBN  0-12-498550-5.