A matematika világában rengeteg fogalom létezik, amelyek elsőre talán távolinak tűnhetnek a mindennapi élettől, mégis mélyen összefonódnak a valóságunkkal. A gráfok és az általuk leírt struktúrák pont ilyenok. Gondoljunk csak a közösségi hálózatokra, ahol emberek kapcsolódnak egymáshoz, vagy az úthálózatokra, amelyek összekötik a városokat. Ezek mind gráfelméleti modellekkel írhatók le. Azonban nemcsak a csomópontok és az összeköttetések léte a fontos, hanem ezeknek a kapcsolatoknak a mennyisége is. A gráf éleinek száma pedig pontosan ezt a mennyiséget fogja meg, egy rendkívül egyszerű, mégis sokoldalú mérőszámként.
Miért is érdemes ezzel a számmal foglalkoznunk? Mert bár első látásra triviálisnak tűnhet megmondani, hány összeköttetés van egy adott struktúrában, a gráf éleinek száma olyan alapvető tulajdonsága a grafoknak, amely számos más jellemzőjük meghatározásához szükséges. Nemcsak a gráftípusok megkülönböztetésében segít, hanem befolyásolja a benne rejlő információk feldolgozásának hatékonyságát, a lehetséges útvonalak számát, vagy akár a struktúra stabilitását is. Érdemes tehát mélyebben elmerülni ebben a fogalomban, mert az egyszerűségében rejlik az ereje.
Ez a leírás arra hivatott, hogy ne csak a definíciót ossza meg veled, hanem bemutassa, hogyan jelenik meg ez a szám a gyakorlatban, milyen összefüggéseket támaszt alá, és miért alapvető fontosságú a gráfelmélet számos területén. Megismerkedünk majd a legegyszerűbb esetektől az összetettebb problémákig, ahol a gráf éleinek számát alapul véve tudunk következtetéseket levonni a grafok szerkezetéről és viselkedéséről.
A gráf éleinek számának bemutatása
A gráfelméletben egy gráf $G$ alapvetően két halmazból áll: egy $V$ csúcshalmazból (vagy más néven pontok, nódusok) és egy $E$ élhalmazból (vagy más néven kötések, ívek). Az élek a csúcsok közötti kapcsolatokat írják le. Az élhalmaz elemei olyan párok, amelyek a csúcsokból állnak. Ha egy élt a $u$ és $v$ csúcsok kapcsolnak össze, akkor ezt az élt gyakran $(u, v)$ vagy ${u, v}$ jelöléssel illetjük, attól függően, hogy a gráf irányított vagy irányítatlan.
A gráf éleinek száma egyszerűen az élhalmaz méretét jelenti. Ezt a számot általában $|E|$ vagy néha $m$ jelöli. Ha egy $G$ gráf éleinek száma $m$, akkor azt írhatjuk, hogy $|E| = m$. Ez a szám egy rendkívül alapvető tulajdonsága a grafoknak, és számos más gráfinvariáns, illetve algoritmus működése függhet tőle.
Például, vegyünk egy egyszerű, irányítatlan gráfot. Legyenek a csúcsok: $V = {A, B, C}$ és az élek: $E = {{A, B}, {B, C}}$. Ebben az esetben a gráf éleinek száma $|E| = 2$.
Egy másik példában, tekintsünk egy irányított gráfot. Legyenek a csúcsok: $V = {1, 2, 3}$ és az élek: $E = {(1, 2), (2, 1), (1, 3)}$. Ebben az esetben a gráf éleinek száma $|E| = 3$.
A gráf éleinek száma nagyon sokféle összefüggésben szerepelhet. Például, egy $n$ csúcsú, egyszerű (nincs benne hurokél vagy többszörös él ugyanazon két csúcs között) és összefüggő gráf esetében az élek minimális száma $n-1$, míg az élek maximális száma $\binom{n}{2}$.
Alapvető fogalmak és definíciók
A gráf éleinek számának megértéséhez elengedhetetlenül fontos tisztázni néhány alapvető gráfelméleti fogalmat. Ezek a fogalmak segítenek pontosan meghatározni, mit értünk egy "grafon" és "élén", és ezáltal mi a gráf éleinek számának pontos jelentése.
Gráftípusok és az élek szerepe
Mielőtt belemerülnénk a számolásba, érdemes megkülönböztetni a leggyakoribb gráftípusokat, mert ez befolyásolhatja, hogyan értelmezzük az éleket és hogyan számoljuk őket:
- Irányítatlan gráfok: Ezekben a grafokban az élek kétirányúak. Ha van egy él a $u$ és $v$ csúcs között, akkor ez azt jelenti, hogy $u$ kapcsolódik $v$-hez és $v$ is kapcsolódik $u$-hoz. Az éleket általában ${u, v}$ párként jelöljük. A gráf éleinek száma egyszerűen ezen párok száma.
- Megjegyzés: Az irányítatlan grafok esetében egy él mindig két különböző csúcsot köt össze.
- Irányított gráfok (digráfok): Ezekben a grafokban az éleknek van iránya. Ha van egy él $u$-ból $v$-be, azt $(u, v)$ párként jelöljük, ami nem feltétlenül jelenti azt, hogy $v$-ből is van él $u$-ba. A gráf éleinek száma itt is az $(u, v)$ rendezett párok száma.
- Megjegyzés: Az irányítottság miatt egy $u$-ból $v$-be és egy $v$-ből $u$-ba irányuló él két különélnek számít, még akkor is, ha ugyanazokat a csúcsokat köti össze.
- Multigráfok: Ezekben a grafokban megengedettek a többszörös élek (ugyanazon két csúcs között több él is futhat) és a hurokélek (egy csúcsból induló és oda visszaérkező él). Ebben az esetben a gráf éleinek száma rendkívül egyszerűen az összes létező él száma, beleértve a többszörös és hurokéleket is.
- Megjegyzés: A standard gráfelméleti problémák és definíciók gyakran feltételezik az egyszerű grafokat, ahol nincsenek többszörös élek és hurokélek. Ha ezek megengedettek, azt általában külön említik.
Alapvető jelölések
Ahogy már említettük, a gráf $G$ éleinek számát általában $|E|$ jelöli. Ha a csúcsok halmazát $V$-vel, az élhalmazt pedig $E$-vel jelöljük, akkor $|V|$ a csúcsok számát, $|E|$ pedig az élek számát jelenti. A gráfelméletben sokszor használják az $n$ jelölést a csúcsok számára ($n = |V|$) és az $m$ jelölést az élek számára ($m = |E|$).
Kapcsolódó fogalmak
Az élek számának megértése szempontjából fontosak a következő fogalmak is:
- Fokszám: Egy csúcs fokszáma az ahhoz az élekhez kapcsolódó "kapcsolatok" száma.
- Iranyítatlan grafban: egy csúcs fokszáma megegyezik a hozzá kapcsolódó élek számával. Hurokélt kétszer számolnak.
- Irányított grafban: egy csúcsnak lehet bemenő (indegree) és kimenő (outdegree) fokszáma.
- Összefüggőség: Egy gráf összefüggő, ha bármely két csúcs között létezik út. Az összefüggőség szorosan kapcsolódik az élek számához: egy $n$ csúcsú, nem üres, összefüggő, egyszerű grafnak legalább $n-1$ éle van.
"Az élek száma nem csupán egy adat, hanem a struktúra rejtett dimenziójának megnyilvánulása, amely meghatározza annak rugalmasságát és kapcsolódási képességét."
A gráf éleinek számának kiszámítása és meghatározása
A gráf éleinek számának meghatározása magától értetődőnek tűnhet: egyszerűen megszámoljuk az éleket az élhalmazban. Azonban vannak speciális esetek és összefüggések, amelyek finomítják ezt a folyamatot, különösen bonyolultabb grafok vagy specifikus tulajdonságok esetén.
Manuális megszámolás
A legegyszerűbb esetben, ha rendelkezésünkre áll a gráf vizuális reprezentációja vagy az élhalmaz explicit listája, az élek számát közvetlenül meg tudjuk határozni.
Például, egy irányítatlan graf csúcsai: $V = {1, 2, 3, 4}$, és az élek listája: $E = {{1, 2}, {1, 3}, {2, 3}, {3, 4}}$.
Ebben az esetben az élek száma $|E| = 4$.
Egy irányított graf csúcsai: $V = {A, B, C}$, és az élek listája: $E = {(A, B), (B, C), (C, A), (A, C)}$.
Itt az élek száma $|E| = 4$.
Fokszámok összege és az élek száma
Az egyik legfontosabb tétel a gráfelméletben a fokszámösszeg-tétel (Handshaking Lemma), amely az élek számát és a csúcsok fokszámát köti össze.
Tétel (Fokszámösszeg-tétel):
Bármely irányítatlan $G = (V, E)$ gráfban a csúcsok fokszámának összege egyenlő az élek számának kétszeresével.
$$\sum_{v \in V} \deg(v) = 2|E|$$
Ahol $\deg(v)$ jelöli a $v$ csúcs fokszámát.
Ez a tétel rendkívül hasznos lehet az élek számának meghatározásához, ha ismerjük a csúcsok fokszámait, vagy fordítva.
- Alkalmazás: Ha egy gráfban a csúcsok fokszámai rendre $d_1, d_2, \dots, d_n$, akkor az élek száma:
$$|E| = \frac{1}{2} \sum_{i=1}^n d_i$$
Például, tekintsünk egy hat csúcsú, egyszerű, irányítatlan gráfot, ahol a csúcsok fokszámai a következők: 3, 2, 4, 2, 3, 2.
A fokszámok összege: $3 + 2 + 4 + 2 + 3 + 2 = 16$.
A fokszámösszeg-tétel alapján az élek száma: $|E| = \frac{16}{2} = 8$.
"A fokszámok összegének fele nem csak az élek számát adja, hanem a gráf belső 'aktivitásának' mértékét is tükrözi, ahol minden él két csúcsot 'köt össze'."
Maximális és minimális élszám speciális grafok esetén
Bizonyos gráftípusok, különösen a csúcshalmaz méretéből kiindulva, rendelkeznek meghatározott maximális vagy minimális élszámmal.
-
Teljes gráf ($K_n$): Egy $n$ csúcsú teljes gráfban minden csúcs össze van kötve minden más csúccsal. Az élek száma ebben az esetben:
$$|E| = \binom{n}{2} = \frac{n(n-1)}{2}$$
Például, egy 4 csúcsú teljes gráf ($K_4$) éleinek száma $\binom{4}{2} = \frac{4 \times 3}{2} = 6$. -
Bipartite gráf: Egy $G = (V, E)$ gráf bipartite, ha a $V$ csúcshalmaz két diszjunkt részhalmazra (partícióra), $V_1$ és $V_2$ osztható úgy, hogy minden él két különböző partícióban lévő csúcsot köt össze. Ha $|V_1| = n_1$ és $|V_2| = n_2$, akkor egy $n_1 + n_2$ csúcsú, teljes bipartite gráf ($K_{n_1, n_2}$) éleinek száma:
$$|E| = n_1 \times n_2$$
Például, a $K_{3,2}$ teljes bipartite gráf éleinek száma $3 \times 2 = 6$. -
Fak: Egy $n$ csúcsú fát (minden nem triviális $u, v$ csúcs között pontosan egy út van) mindig $n-1$ él alkot.
$$|E| = n-1$$
Ez egyben az $n$ csúcsú, összefüggő, egyszerű grafok éleinek minimális száma is.
Irányított grafok speciális esetei
Irányított grafok esetén a fokszámösszeg-tételnek van egy analógja: a bemenő fokszámok összege megegyezik a kimenő fokszámok összegével, és ez az érték egyenlő az élek számával.
$$\sum_{v \in V} \deg_{in}(v) = \sum_{v \in V} \deg_{out}(v) = |E|$$
Ahol $\deg_{in}(v)$ a $v$ csúcs bemenő fokszáma, és $\deg_{out}(v)$ a $v$ csúcs kimenő fokszáma.
Gráfok éleinek számának táblázatos összefoglalása
Az alábbi táblázat összefoglalja a leggyakoribb gráftípusok és néhány specifikus struktúra éleinek számát, feltételezve, hogy $n$ csúcs van jelen, hacsak másként nincs megadva.
| Gráftípus / Tulajdonság | Jelölés | Élek száma ($|E|$) | Megjegyzés |
| :—————————————————— | :————————————– | :———————————————— | :——————————————————————————– |
| Egyszerű, irányítatlan gráf, $n$ csúccsal | Általános | $m$ | Bármilyen $0 \le m \le \binom{n}{2}$ lehetséges |
| Teljes gráf, $n$ csúccsal | $K_n$ | $\binom{n}{2} = \frac{n(n-1)}{2}$ | Minden csúcs össze van kötve minden más csúccsal. |
| Bipartite gráf, $V_1$ és $V_2$ partíciókkal, $|V_1|=n_1, |V_2|=n_2$ | $G=(V_1 \cup V_2, E)$ | $m$, ahol $0 \le m \le n_1 n_2$ | Az élek csak különböző partíciókban lévő csúcsokat köthetnek össze. |
| Teljes bipartite gráf, $n_1, n_2$ csúccsal | $K_{n_1, n_2}$ | $n_1 n_2$ | Minden lehetséges párosítás össze van kötve. |
| Fa, $n$ csúccsal | $T$ | $n-1$ | Összefüggő, nem tartalmaz ciklust. |
| Kör, $n$ csúccsal | $C_n$ | $n$ | Pontosan egy $n$-hosszú út, ahol az út végpontjai össze vannak kötve. |
| Irányított gráf, $n$ csúccsal | Általános digráf | $m$ | Bármilyen $0 \le m \le n(n-1)$ lehetséges (egyszerű digráf esetén) |
| Teljes irányított gráf, $n$ csúccsal | $K_n^{dir}$ | $n(n-1)$ | Minden csúcs és minden más csúcs között két irányú él van. |
| Egyirányú kör, $n$ csúccsal | $C_n^{dir}$ | $n$ | $v_1 \to v_2 \to \dots \to v_n \to v_1$ |
| Huroktalan, többszörös élek nélküli (egyszerű) gráf, $n$ csúccsal | Egyszerű gráf | $m$ | Speciális definíciók szükségesek a maximális és minimális élszámhoz. |
| Multigráf, $n$ csúccsal | Multigráf | $m$ | Megengedettek a többszörös élek és hurokélek. Az élszám felső határa nincs. |
Példák különböző gráftípusokra
1. Összefüggő, egyszerű, irányítatlan gráfok:
Legyen $n=5$ csúcsunk.
- Minimális élszám egy összefüggő grafhoz: $n-1 = 5-1 = 4$ (ez egy fa).
- Maximális élszám egy egyszerű grafhoz: $\binom{5}{2} = \frac{5 \times 4}{2} = 10$ (ez egy $K_5$).
Tehát egy 5 csúcsú összefüggő, egyszerű, irányítatlan graf éleinek száma $4 \le |E| \le 10$.
2. Bipartite gráfok:
Tekintsünk egy $K_{3,4}$ teljes bipartite gráfot.
Itt $n_1=3$ és $n_2=4$.
Az élek száma: $|E| = n_1 \times n_2 = 3 \times 4 = 12$.
3. Irányított grafok:
Legyen $n=3$ csúcsunk egy egyszerű irányított grafban.
- Maximális élszám: $n(n-1) = 3(3-1) = 3 \times 2 = 6$. Ez a $K_3^{dir}$ teljes irányított graf.
Például: $(1,2), (2,1), (1,3), (3,1), (2,3), (3,2)$.
"Az élek maximális és minimális száma nem csupán a csúcsok számától függ, hanem attól is, hogy a struktúra milyen 'szabadságot' enged meg a kapcsolatok kialakításában."
A gráf éleinek számának jelentősége és alkalmazásai
A gráf éleinek száma, bár elsőre csupán egy egyszerű számlálási eredménynek tűnhet, alapvető fontosságú a gráfelmélet számos területén, és széles körben alkalmazható a valós problémák modellezésében. Az élek számának ismerete befolyásolja a grafok tulajdonságainak megértését, az algoritmusok hatékonyságát és a lehetséges struktúrák elemzését.
Algoritmusok komplexitása
Számos gráfinformatikai algoritmus futási idejét az élek és csúcsok száma határozza meg. A legtöbb standard gráfaloritmus futási idejét $O(V+E)$ vagy $O(E \log V)$ vagy $O(V^2)$, $O(E^2)$ formában fejezik ki, ahol $V$ a csúcsok száma, $E$ pedig az élek száma.
- Példák:
- Szélességi keresés (BFS) és Mélységi keresés (DFS): Ezek az alapvető gráfbejáró algoritmusok általában $O(V+E)$ időkomplexitással futnak. Az élek száma itt kulcsfontosságú, mert minden élt meg kell vizsgálni a csúcsok elérése érdekében.
- Dijkstra algoritmusa: Elsősorban a súlyozott grafok legrövidebb útjainak megtalálására használják. Prioritásos sorral megvalósítva a komplexitása $O(E + V \log V)$, míg egyszerű tömbbel $O(V^2)$. Itt is látjuk, hogy az élek száma ($E$) jelentősen befolyásolja a futásidőt.
- Floyd-Warshall algoritmusa: Minden csúcspár közötti legrövidebb utat határozza meg. Időkomplexitása $O(V^3)$. Itt az élek száma nem jelenik meg közvetlenül a komplexitásban, de a gráf denzitása (az élek sűrűsége) alapvetően meghatározza a gráf felépítését, ami befolyásolhatja az effektív futásidőt.
"Az algoritmusok hatékonysága sokszor az élek számával arányosan nő, ami arra utal, hogy a 'kapcsolatok' száma meghatározó tényező a számítási feladatok során."
Gráfok osztályozása és tulajdonságai
Az élek száma segít a grafok különböző tulajdonságainak osztályozásában és megértésében:
-
Sűrű és ritka grafok:
- Egy ritka graf olyan gráf, amelyben az élek száma közel van a minimális lehetséges számhoz, például $E \approx V$. Az ilyen grafoknak kevés "redundáns" kapcsolatuk van. Például a hálózati topológiák, a fák, a hálózatok gyakran ritkák.
- Egy sűrű graf olyan gráf, amelyben az élek száma közel van a maximálisan lehetséges számhoz, például $E \approx V^2$. Ezekben a grafokban sok a lehetséges kapcsolat. Például a teljes gráfok vagy az elágazóan összekapcsolt rendszerek lehetnek sűrűek. A sűrűség fogalma kritikus lehet a problémamegoldás stratégiák kiválasztásában.
-
Összefüggőség és komponensek:
Az élek számának nagysága az összefüggőséghez is kapcsolódik. Ahogy említettük, egy $n$ csúcsú, összefüggő grafnak legalább $n-1$ éle van. Ha egy grafban ennél kevesebb él van, akkor nem lehet összefüggő. Az élek száma és azok elhelyezkedése meghatározza a grafban lévő összefüggő komponensek számát is. Minél több az él, annál valószínűbb, hogy a graf egyetlen nagy összefüggő komponensből áll. -
Ciklusok és csatolások:
Az élek száma összefüggésben van a grafban lévő ciklusok (körök) számával is. Egy $n$ csúcsú, összefüggő, egyszerű grafban, ha az élek száma pontosan $n-1$, akkor a grafnak nincs ciklusa (ez egy fa). Ha az élek száma $n$ vagy annál több, akkor a grafnak mindenképpen tartalmaznia kell legalább egy ciklust. Az élek és csúcsok aránya (szorzata) befolyásolja a "ciklikus komplexitást".
Valós Világbeli Alkalmazások
A "gráf éleinek száma" sok rejtett problémában jelenik meg:
- Közösségi hálózatok: Emberek (csúcsok) és barátságok/kapcsolatok (élek) modellezésekor az élek száma megadja a hálózat "méretét" és "sűrűségét", ami befolyásolja az információ terjedését, a csoportok kialakulását.
- Térképek és útvonaltervezés: Városok (csúcsok) és utak (élek) modellezésekor az élek száma (vagy az utak száma) befolyásolja a lehetséges útvonalak számát és a navigációs algoritmusok hatékonyságát.
- Biologia és kémia: Molekuláris struktúrák, fehérje-interakciók (csúcsok) és kölcsönhatásaik (élek) elemzésekor az élek száma a rendszerek összetettségét jelzi.
- Számítógépes hálózatok: Számítógépek (csúcsok) és hálózati kapcsolatok (élek) ábrázolásakor az élek száma a hálózat robusztusságát és adatátviteli képességét befolyásolja.
- Logisztika és szállítás: Raktárak, elosztóhelyek (csúcsok) és szállítási útvonalak (élek) modellezésekor az élek száma a szállítási hálózat összetettségét jelzi.
"A hálózatok 'gazdagsága' nem csak a csomópontok számában rejlik, hanem abban is, hogy ezen csomópontok hogyan és milyen mértékben vannak összekötve – ezt pedig az élek száma kvantifikálja."
Néhány további érdekesség az élek számával kapcsolatban
A gráfok éleinek számával kapcsolatosan számos érdekesség és speciális probléma merül fel, amelyek tovább árnyalják ennek az alapvető gráfinvariánsnak a jelentőségét. Ezek a szempontok gyakran vezetnek mélyebb elméleti kutatásokhoz vagy specifikus algoritmusok kidolgozásához.
Szupergrófok és altengelyek
Egy adott gráfhoz kapcsolódó fogalmak lehetnek a szupergráfok és altengelyek.
- Szupergráf: Ha $G_1 = (V_1, E_1)$ és $G_2 = (V_2, E_2)$ két gráf, akkor $G_2$ szupergrófja $G_1$-nek, ha $V_1 \subseteq V_2$ és $E_1 \subseteq E_2$. Ebben az esetben az élek számának viszonya egyértelmű: $|E_1| \le |E_2|$.
- Altengely: Fordított viszonyban, $G_1$ altengelye $G_2$-nek, ha $V_1 \subseteq V_2$ és $E_1 \subseteq E_2$.
Ezek a fogalmak arra utalnak, hogy az élek számahogyan viszonyul a struktúrák bővüléséhez vagy szűküléséhez.
Ramsey-elmélet és gráfturbológia
Bár a Ramsey-elmélet elsősorban nem az élek számának pontos meghatározására összpontosít, az élek számára vonatkozó kérdések szorosan összefüggenek azzal, hogy bizonyos számú él hogyan garantál bizonyos mintázatokat a grafokban. Például, egy elég nagy számú éllel rendelkező grafban mindig biztosan találunk egy bizonyos méretű teljes algráfot (klikk), függetlenül attól, hogyan rendeződtek az élek. Itt az élek lokális eloszlása és nemzetközi száma játszik szerepet.
A gráfturbológia egy újabb terület, amely a gráfok dinamikus fejlődését vizsgálja. Az élek számának növekedése vagy csökkenése meghatározza a gráf fejlődési útját, például egy növekedési folyamat során új élek jöhetnek létre.
Élek száma és a gráf tulajdonságainak levezetése
Gyakran előfordul, hogy a gráf éleinek számából következtetni lehet a gráf bizonyos tulajdonságaira, anélkül, hogy ismernénk az összes pontos kapcsolatot.
- Gyakorlati példa: Ha egy hálózati rendszer (pl. erőművek és vezetékek) tervezésekor tudjuk, hogy az élek maximális száma korlátozott (pl. anyagi vagy fizikai okok miatt), akkor ez a korlátozás befolyásolja, milyen rugalmas és redundáns lesz a hálózat. Például, ha a rendszernek $N$ csúcsú, és csak $N-1$ éle van, akkor tudjuk, hogy a rendszer "minimálisan" összekapcsolt, és egyetlen él eltávolítása is ketté választhatja a rendszert.
Az élek és a csúcsok aránya mint mérőszám
Nemcsak az élek vagy a csúcsok abszolút száma fontos, hanem az arányuk is. A $\frac{|E|}{|V|}$ hányados sok mindent elárul a graf "sűrűségéről".
- Ha $\frac{|E|}{|V|} \approx 1$, akkor a graf ritka, valószínűleg fa-szerű szerkezetet mutat.
- Ha $\frac{|E|}{|V|} \approx \frac{n}{2}$, akkor a graf már sűrűbbnek tekinthető.
- Egy $n$ csúcsú teljes grafban $\frac{|E|}{|V|} = \frac{n(n-1)/2}{n} = \frac{n-1}{2}$, ami $n$ növekedésével lineárisan nő.
Ez az arány rendkívül hasznos lehet a különböző méretű grafok összehasonlításában, vagy amikor egy generált graf tulajdonságait akarjuk becsülni.
"A struktúra 'információs tartalma' nemcsak a felépítő elemek számában, hanem azok egymáshoz való viszonyulásának mértékében is rejlik, amit az élek és csúcsok aránya jól megragad."
Gyakran ismételt kérdések (GYIK)
Miben különbözik az élek száma egy irányítatlan és egy irányított grafban?
H6: Egy irányítatlan grafban az élek száma ${u,v}$ alakú párok halmazának elemszáma, ahol az él $u$ és $v$ között fut. Egy irányított grafban az élek száma $(u,v)$ alakú rendezett párok halmazának elemszáma, ahol az él $u$-ból indul és $v$-be érkezik. Ez azt jelenti, hogy egy irányított grafban egy $u$-ból $v$-be és egy $v$-ből $u$-ba futó él két külön élnek számít, míg egy irányítatlan grafban ez egyetlen él.
Számít-e a hurokél (egy csúcsot önmagával összekötő él) az élek számánál?
H6: Igen, általában a hurokél is számít az élek számánál, ahogy a többszörös élek is (ugyanazon két csúcs között többször futó élek), amennyiben a gráfot multigráfként definiáljuk. Egyszerű grafok esetén a hurokélek és a többszörös élek nem megengedettek. Ha nem specifikálják, hogy egyszerű grafról van szó, akkor érdemes tisztázni, hogy a hurokélek beleszámítanak-e. A fokszámösszeg-tételben a hurokél a csúcs fokszámát kétszer növeli.
Hogyan kapcsolódik az élek száma a gráf összefüggőségéhez?
H6: Egy $n$ csúcsú, nem üres, összefüggő, egyszerű, irányítatlan grafnak legalább $n-1$ éle van. Ha egy ilyen grafnak pontosan $n-1$ éle van, akkor a graf egy fa, és nincs benne ciklus. Ha kevesebb mint $n-1$ éle van, akkor a graf nem lehet összefüggő. Az élek számának növelése általában növeli a graf összefüggőségét és csökkenti az összefüggő komponensek számát.
Mi az a "teljes gráf" és hány éle van?
H6: Egy $n$ csúcsú teljes gráf egy olyan egyszerű, irányítatlan gráf, amelyben minden csúcs össze van kötve minden más csúccsal. Ennek megfelelően, az élek száma egy $n$ csúcsú teljes grafban $\binom{n}{2} = \frac{n(n-1)}{2}$.
Milyen módon tudjuk meghatározni az élek számát, ha csak a csúcsok fokszámait ismerjük?
H6: A fokszámösszeg-tétel (Handshaking Lemma) alapján, bármely irányítatlan grafban a csúcsok fokszámainak összege megegyezik az élek számának kétszeresével ($ \sum_{v \in V} \deg(v) = 2|E| $). Tehát az élek száma $ |E| = \frac{1}{2} \sum_{v \in V} \deg(v) $.
