Număr mixt

Un grafic mixt G = (V, E, A) este un obiect matematic format dintr-un set de vârfuri (sau noduri) V, un set de muchii (nedirecționate) E și un set de muchii direcționate (sau arce) A. [ 1]

Definiții și notație

Informații suplimentare: Grafic (matematică)

Luați în considerare vârfurile învecinate . O margine orientată se numește arc , o margine cu o orientare, care este notat cu sau (merită remarcat faptul că aceasta este coada și acesta este capul arcului). [2] O muchie nedirecționată , sau pur și simplu o muchie , se numește muchie fără orientare și este notă cu sau . [2] $u,v\in V$ ${\displaystyle {\overrightarrow {uv)}}$ ${\displaystyle (u,v))$ $u$ $v$ ${\displaystyle uv)$ $[u,v]$

Informații suplimentare: margini multiple

Informații suplimentare: Buclă (teoria grafurilor)

Ca exemplu de aplicație, nu vom lua în considerare ciclurile sau marginile multiple ale graficelor mixte.

O cale într-un grafic mixt este o succesiunede vârfuri și muchii/arce astfel încât, pentru toți indicii,muchie a graficului, fie elementuleste un arc al graficului. Această cale este o cale dacă nu are muchii, arce sau vârfuri repetate, cu excepția, eventual, a primului și ultimului vârf. O cale este închisă dacă primul și ultimul vârf sunt aceleași, iar o cale închisă este un ciclu dacă nu are alte vârfuri repetate decât primul și ultimul. Un grafic mixt este aciclic dacă nu conține un ciclu. ${\displaystyle v_{0},c_{1},v_{1},c_{2},v_{2},\dots,c_{k},v_{k))$ ${\displaystyle i)$ ${\displaystyle c_{i}=v_{i}v_{i+1))$ ${\displaystyle c_{i}={\overrightarrow {v_{i}v_{i+1)}))$

Plansa de colorat

Informații suplimentare: Colorarea graficului

Colorarea unui grafic mixt poate fi considerată ca etichetare sau atribuire de culori diferite (unde este un întreg pozitiv) vârfurilor graficului mixt. [3] Vârfurilor conectate printr-o muchie trebuie să li se atribuie culori diferite. Culorile pot fi reprezentate prin numere de la 1 la , iar pentru un arc direcționat, coada arcului trebuie să fie indicată printr-un număr mai mic decât capul arcului. [3] $k$ $k$ $k$

Exemplu

De exemplu, luați în considerare figura din dreapta. K-culori disponibile pentru colorarea graficului nostru mixt: . Deoarece și sunt conectate printr-o margine, acestea trebuie să aibă culori sau numere diferite ( și sunt etichetate cu 1 și, respectiv, 2). Avem și un arc de la până la . Deoarece avem de-a face cu un arc în care orientarea dictează ordinea numerelor, trebuie să etichetăm coada ( ) cu o culoare mai mică (sau un număr întreg din setul nostru) decât capul ( ) arcului nostru. ${\displaystyle \{1,2,3\))$ ${\displaystyle u)$ ${\displaystyle v)$ ${\displaystyle u)$ ${\displaystyle v)$ ${\displaystyle v)$ ${\displaystyle w)$ ${\displaystyle v)$ ${\displaystyle w)$

Colorare puternică și slabă

Colorarea proprie ( puternice) a unui grafic mixt este o funcție $k$

${\displaystyle c:V\rightarrow [k]}$ , unde astfel încât , dacă , și , dacă . [unu] $[k]:={1,2,\dots,k)$ ${\displaystyle c(u)\neq c(v))$ ${\displaystyle uv\in E)$ ${\displaystyle c(u)<c(v))$ ${\displaystyle {\overrightarrow {uv}}\in A}$

Putem relaxa starea arcurilor noastre. Apoi putem considera k-colorarea slabă adecvată a graficului mixt ca o funcție

${\displaystyle c:V\rightarrow [k]}$ , unde astfel încât , dacă , și , dacă . [1] Revenind la exemplul nostru, aceasta înseamnă că putem eticheta capul și coada cu numărul întreg pozitiv 2. $[k]:={1,2,\dots,k)$ ${\displaystyle c(u)\neq c(v))$ ${\displaystyle uv\in E)$ ${\displaystyle c(u)\leq c(v))$ ${\displaystyle {\overrightarrow {uv}}\in A}$ $(v,w)$

Existenta

Pentru un grafic mixt, o colorare poate exista sau nu. Pentru ca un grafic mixt să fie colorabil, nu trebuie să conțină cicluri direcționate. [2] Dacă există o astfel de colorare, atunci notăm cel mai mic necesar pentru a ne colora corect graficul ca număr cromatic , notat cu . [2] Putem număra numărul de colorări proprii ca o funcție polinomială a . Acesta se numește polinomul cromatic al graficului nostru (prin analogie cu polinomul cromatic al graficelor nedirecționate) și poate fi notat ca . [unu] $k$ $k$ $k$ ${\displaystyle \chi (G))$ $k$ $k$ $G$ ${\displaystyle \chi _{G}(k))$

Calculul polinoamelor cromatice slabe

Formula de ștergere-contracție poate fi utilizată pentru a calcula polinoame cromatice slabe ale graficelor mixte. Această metodă implică îndepărtarea unei muchii sau arc și micșorarea (sau unirea) vârfurilor rămase pe acea muchie (sau arc) pentru a forma un singur vârf. [1] După îndepărtarea unei muchii dintr-un grafic mixt, obținem un grafic mixt . [1] Putem nota această îndepărtare a muchiei ca . În mod similar, prin eliminarea unui arc dintr-un grafic mixt, obținem , unde putem nota eliminarea ca . [1] În plus, putem desemna abrevierea și ca și respectiv . [1] Din afirmațiile de mai sus, [1] obținem următoarele ecuații pentru calcularea polinomului cromatic al unui grafic mixt: $e$ $G=(V,E,A)$ $(V,Ee,A)$ $e$ $Ge$ $A$ $(V,E,Aa)$ $A$ $Ga$ $e$ $A$ $G/e$ $G/a$

${\displaystyle \mathrm {X} _{G}(k)=\chi _{Ge}(k)-\chi _{G/e}(k))$ [unu]
${\displaystyle \chi _{G}(k)=\chi _{Ga}(k)+\chi _{G/a}(k)-\chi _{G_{a}}(k) }$ [unu]

Aplicații

Problemă de planificare

Graficele mixte pot fi folosite pentru a modela sarcinile de programare a muncii în care sarcinile trebuie colectate, sub rezerva anumitor constrângeri de timp. În acest tip de sarcină, marginile nedirecționate pot fi folosite pentru a modela constrângerea conform căreia două sarcini sunt incompatibile (nu pot fi executate în același timp). Marginile direcționate pot fi folosite pentru a modela constrângeri de prioritate, în care o sarcină trebuie finalizată înainte de alta. Un graf definit în acest fel dintr-o problemă de planificare se numește graf disjunctiv. Problema de colorare a graficului mixt poate fi utilizată pentru a găsi programul de lungime minimă pentru a finaliza toate sarcinile. [2]

Inferența bayesiană

Graficele mixte sunt, de asemenea, folosite ca modele grafice pentru inferența bayesiană . În acest context, un graf mixt aciclic (fără cicluri de muchii direcționate) se mai numește și graf în lanț. Marginile direcționate ale acestor grafice sunt folosite pentru a indica o relație cauzală între două evenimente, în care rezultatul primului eveniment afectează probabilitatea celui de-al doilea eveniment. Marginile nedirecționate indică o corelație non-cauzoală între două evenimente. O componentă conexă a unui subgraf nedirecționat al unui graf în lanț se numește lanț. Un graf în lanț poate fi convertit într-un graf nedirecționat prin construirea graficului său moral , un graf nedirecționat format dintr-un graf în lanț prin adăugarea de muchii nedirecționate între perechi de vârfuri care au muchii de ieșire în același lanț, fără a ține cont de orientarea muchiilor direcționate. [patru]

Note

↑ 1 2 3 4 5 6 7 8 9 10 11 Matthias Beck, Daniel Blado, Joseph Crawford, Taïna Jean-Louis, Michael Young. Despre polinoame cromatice slabe ale graficelor mixte // Grafice și combinatorie. — 01-01-2015. — Vol. 31 , iss. 1 . — P. 91–98 . — ISSN 1435-5914 . - doi : 10.1007/s00373-013-1381-1 .
↑ 1 2 3 4 5 B. Ries. Colorarea unor clase de grafice mixte (engleză) // Matematică aplicată discretă. - 01-01-2007. — Vol. 155 , iss. 1 . — P. 1–6 . — ISSN 0166-218X . - doi : 10.1016/j.dam.2006.05.004 .
↑ 1 2 Pierre Hansen, Julio Kuplinsky, Dominique de Werra. Colorări grafice mixte (engleză) // Metode matematice de cercetare operațională. - 1997-02-01. — Vol. 45 , iss. 1 . — P. 145–160 . — ISSN 1432-5217 . - doi : 10.1007/BF01194253 .
↑ Robert G. Cowell, Philip Dawid, Steffen L. Lauritzen, David J. Spiegelhalter. Rețele probabilistice și sisteme experte: metode de calcul exacte pentru rețele bayesiene . — Springer Science & Business Media, 2007-07-16. — 340 s. - ISBN 978-0-387-71823-1 .

Link -uri

Weisstein, Eric W. „Grafic mixt” MathWorld