Vikipedio:Projekto matematiko/Krucanta nombro

El Vikipedio

Ĉi tiu artikolo montras stilajn aŭ/kaj gramatikajn aŭ/kaj strukturajn problemojn kaj bezonas poluradon por konformi al pli bona nivelo de kvalito. Post plibonigo movu la artikolon al
Krucanta nombro
(eble la nomo mem bezonas korekton) Se la ligo estas ruĝa, vi povas movi la artikolon. Se la ligo estas blua, la alia artikolo pri la temo jam ekzistas kaj tiun kaj ĉi tiun artikolon necasas kunigi.

En matematiko, krucantaj nombroj ekesti en du rilatantaj ĉirkaŭtekstoj: en noda teorio kaj en grafeteorio.

Enhavo

1 Krucantaj nombroj en noda teorio
2 Krucantaj nombroj en grafeteorio
- 2.1 Komplekseco
- 2.2 La krucanta nombra neegalaĵo
  - 2.2.1 Pruvo de krucanta nombra neegalaĵo
3 Referencoj

[redaktu] Krucantaj nombroj en noda teorio

En noda teorio, la krucanta nombro estas ekzemplo de noda invarianto. Noda krucanta nombro estas simple la (plej malalta, plej suba) nombro de (navokruciĝoj, navokruciĝas) de (ĉiu, iu) figuro de la nodo.

Per vojo de ekzemplo, la malnodo havas krucanta nombra nulo, la _trefoil_ nodo tri kaj la (cifero, figuro)-ok nodo kvar. Estas ne alia (nodoj, nodas) kun krucanta nombro ĉi tiu malalta kaj (justa, ĵus) du (nodoj, nodas) havi krucanta nombro 5, sed la nombro de (nodoj, nodas) kun aparta krucanta nombro (multigas, pligrandiĝoj, pligrandiĝas) rapide kiel ni iri pli alta.

(Baremoj, Baremas, Tabeloj, Tabelas, Tabloj, Tablas) de primaj nodoj estas tradicie (indeksita, indicita) per krucanta nombro, kun suba indico al indiki kiu aparta nodo el tiuj kun ĉi tiu multaj (navokruciĝoj, navokruciĝas) estas intencita (ĉi tiu sub-(ordenanta, mendanta, ordanta, dimensianta, komandanta, ordigo) estas ne bazita sur io en aparta, escepti (tiu, ke, kiu) toraj nodoj estas listita unua). La listante iras 3₁ (la _trefoil_ nodo), 4₁ (la (cifero, figuro)-ok nodo), 5₁, 5₂, 6₁, kaj tiel plu Ĉi tiu (mendi, ordo) havas ne ŝanĝita grave ekde P. G. _Tait_ (publikigita, publikigis) tabelo de (nodoj, nodas) en 1877.

[redaktu] Krucantaj nombroj en grafeteorio

La krucanta nombro _cr_(G) de (grafikaĵo, grafeo) G estas la (plej malalta, plej suba) nombro de (navokruciĝoj, navokruciĝas) de _planar_ figuro de la (grafikaĵo, grafeo) G. Ekzemple, (grafikaĵo, grafeo) estas _planar_ se kaj nur se ĝia krucanta nombro estas nulo.

[redaktu] Komplekseco

En ĝenerala, (determinanta, difinanta) la krucanta nombro de (grafikaĵo, grafeo) estas peza; _Garey_ kaj _Johnson_ montris en 1983 (tiu, ke, kiu) ĝi estas NP-peza problemo. Fakte, _Petr_ _Hlin_ě_ný_ montris en 2003 (tiu, ke, kiu) la problemo restas NP-peza (eĉ, ebena, para) kiam limigis al kubaj grafeoj, kiu havi malalta grado.

Sur la pozitiva flanko, estas kompetenta (O(|V|²)) algoritmo por (determinanta, difinanta) se la krucanta nombro estas malpli ol (fiksis, neŝanĝebligita) konstanto k; ĝi restas malfacila por pli granda k, kiel |V|/2. Estas ankaŭ kompetenta proksimuma kalkulado (algoritmoj, algoritmas) por komputanta la krucanta nombro de (grafikaĵoj, grafeoj) de barita grado. En praktika heŭristiko (algoritmoj, algoritmas) estas uzitaj, kiel la simpla algoritmo kiu startas sen randoj kaj daŭre adicias ĉiu nova rando kvazaŭ (tiu, ke, kiu) produktas la malplej aldona (navokruciĝoj, navokruciĝas) ebla.

[redaktu] La krucanta nombra neegalaĵo

La tre utila krucanta nombra neegalaĵo, esplorita sendepende per _Ajtai_, _Chvatal_, _Newborn_, kaj _Szemerédi_ [1] kaj per _Leighton_ [2], asertas (tiu, ke, kiu) se (grafikaĵo, grafeo) G (nedirektita, sen cikloj aŭ multaj randoj) kun n verticoj kaj e randoj havas multaj randoj, en la (senso, senco) (tiu, ke, kiu) se

$e > 7.5 n,\,$

tiam ni havi

$\operatorname{cr}(G) \geq \frac{e^3}{33.75 n^2}.\,$

La konstanto 33.75 estas la plej bona sciata al dato, kaj estas pro al _Pach_ kaj _Tóth_ [3]; la konstanto 7.5 povas esti malaltigita al 4, sed je la elspezo de anstataŭiganta 33.75 kun la pli malbona konstanto de 64.

La motivado de _Leighton_ en studantaj krucantaj nombroj estis por aplikoj al _VLSI_ dizajno en teoria komputiko. Poste, Sikuloj [4] ankaŭ komprenis (tiu, ke, kiu) ĉi tiu neegalaĵo liveris tre simplaj pruvoj de iu grava (teoremoj, teoremas) en _incidence_ geometrio, kiel _Beck_'s teoremo kaj la _Szemerédi_-_Trotter_ teoremo.

[redaktu] Pruvo de krucanta nombra neegalaĵo

Ni unua doni prepara taksi: por (ĉiu, iu) (grafikaĵo, grafeo) G kun n verticoj kaj e randoj, ni havi

$\operatorname{cr}(G) \geq e - 3n.\,$

Al pruvi ĉi tiu, konsideri figuro de G kiu havas akurate _cr_(G) (navokruciĝoj, navokruciĝas). Ĉiu de ĉi tiuj (navokruciĝoj, navokruciĝas) povas esti forprenita per forprenanta rando de G. Tial ni povas trovi (grafikaĵo, grafeo) kun almenaŭ $e-\operatorname{cr}(G)$ randoj kaj n verticoj sen (navokruciĝoj, navokruciĝas), kaj estas tial ebena grafeo. Sed de Eŭlera formulo ni devas tiam havi $e-\operatorname{cr}(G) \leq 3n$ , kaj la pretendi sekvas. (Fakte ni havi $e-\operatorname{cr}(G) \leq 3n-6$ por n ≥ 3).

Al ricevi la reala krucanta nombra neegalaĵo, ni nun uzi probableca argumento. Ni estu 0 < p < 1 esti probabla parametro al elektiĝi poste, kaj konstrui hazarda subgrafeo H de G per permesanta ĉiu vertico de G al (mensogi, kuŝi) en H sendepende kun probablo p, kaj permesanta rando de G al (mensogi, kuŝi) en H se kaj nur se ĝia du verticoj estis elektita al (mensogi, kuŝi) en H. Estu $e H$ signifi la nombro de randoj de H, kaj estu $n H$ signifi la nombro de verticoj.

Nun konsideri figuro de G kun _cr_(G) (navokruciĝoj, navokruciĝas). Ni (majo, povas) alpreni (tiu, ke, kiu) (ĉiu, iu) du randoj en ĉi tiu figuro kun komuna vertico estas disa, alie ni povita interŝanĝi la sekcanta (partoj, partas) de la du randoj kaj redukti la krucanta nombro per unu. Tial ĉiu krucanta en ĉi tiu figuro engaĝas kvar klaraj verticoj de G.

Ekde H estas subgrafeo de G, ĉi tiu figuro enhavas figuro de H; estu $\operatorname{cr}_H$ signifi la nombro de (navokruciĝoj, navokruciĝas) de ĉi tiu hazarda grafeo. Per la prepara krucanta nombra neegalaĵo, ni havi

$\operatorname{cr}_H \geq e_H - 3n_H.$

Prenante (ekspektoj, ekspektas) ni ricevi

${\Bbb E}(\operatorname{cr}_H) \geq {\Bbb E(e_H)} - 3 {\Bbb E}(n_H).$

Ekde ĉiu de la n verticoj en G havis probablo p de estante en H, ni havi ${\Bbb E}(n_H) = pn$ . Simile, ekde ĉiu de la randoj en G havas probablo $p 2$ de cetera en H (ekde ambaŭ (finpunktoj, finaj punktoj) (bezoni, bezono, necesa) al resti en H), tiam ${\Bbb E}(e_H) = p^2 e$ . Fine, ĉiu krucanta en la figuro de G havas probablo $p 4$ de cetera en H, ekde ĉiu krucanta engaĝas kvar verticoj, kaj (do, tiel) ${\Bbb E}(\operatorname{cr}_H) = p^4 \operatorname{cr}(G)$ . Tial ni havi

$p^4 \operatorname{cr}(G) \geq p^2 e - 3 p n.\,$

Se ni nun aro p al egala 4n/e (kiu estas malpli ol unu, ekde ni alpreni (tiu, ke, kiu) e estas pli granda ol 4n), ni ricevi post iu algebro

$\operatorname{cr}(G) \geq e^3 / 64 n.\,$

_Slight_ bonmaniereco de ĉi tiu argumento permesas unu al anstataŭigi 64 per 33.75 kiam e estas pli granda ol 7.5 n; vidi [3].

[redaktu] Referencoj

Sinjoro _Ajtai_, V. _Chvátal_, Sinjoro _Newborn_, kaj E. _Szemerédi_, Krucanta-libera (subgrafeoj, subgrafeas), Analoj de Diskreta Matematiko 12 (1982), 9-12.
T. _Leighton_, Komplekseco (Eldonas, Aferoj) en _VLSI_, Fundamentoj de Komputanta Serio, _MIT_ Premi, Kembriĝo (Britio), Ma, 1983.
J. _Pach_ kaj G. _Tóth_: (Grafikaĵoj, Grafeoj) desegnita kun kelkaj (navokruciĝoj, navokruciĝas) por rando, _Combinatorica_ 17 (1997), 427-439.
L. A. Sikuloj: Krucantaj nombroj kaj peza _Erdos_ (problemoj, problemas) en diskreta geometrio, Kombinatoriko, Probablo kaj Komputanta 6 (1997), 353-358.
M.R. _Garey_ kaj D.S. _Johnson_. Krucanta Nombro estas (Np, NP)-Plenumi. _SIAM_ J. _Alg_. _Discr_. _Meth_. 4, p.312-316. 1983.
_Petr_ _Hlin_ě_ný_. Krucanta Nombro Estas Peza por Kuba (Grafikaĵoj, Grafeoj). _MFCS_ 2004: 772-782. 2003.

Elŝutita el "http://eo.wikipedia.org../../../p/r/o/Vikipedio%7EProjekto_matematiko_Krucanta_nombro_34bb.html"

Kategorioj: Artikoloj por polurado kaj movo | Noda teorio | Grafeteorio

Vikipedio:Projekto matematiko/Krucanta nombro

El Vikipedio

Enhavo

[redaktu] Krucantaj nombroj en noda teorio

[redaktu] Krucantaj nombroj en grafeteorio

[redaktu] Komplekseco

[redaktu] La krucanta nombra neegalaĵo

[redaktu] Pruvo de krucanta nombra neegalaĵo

[redaktu] Referencoj

Views

Navigado

Serĉu

Aliaj lingvoj