Можа хто-небудзь растлумачыць мне значэнне $ е \ Leq 3v-6 $ ў тэорыі графаў?

Я вучуся для канчатковага і мой падручнік часта выкарыстоўваецца раўнанне <�Пралёт клас = "матэматыка-кантэйнер"> $$ е \ ле 3v-6 $$ (Здаецца, тэорыя ці следства) для некаторых з тэорыі доказаў граф, але я не магу знайсці дзе-небудзь пра тое, дзе гэта раўнанне атрымліваецца з таму робіць яго цяжка для мяне, каб паспрабаваць выкарыстоўваць яго як частку рашэньня.

Можа хто-то калі ласка, скажыце мне, як гэта атрымана, і чаму гэта важна? </Р>

Вялікі дзякуй!

0

5 адказы

Для простага сувязнога планарных графа з $ v \ Ge 3 $ вяршыні і <�пралёт клас = "Math-кантэйнер"> $ E $ абзы, <�Клас пядзі = "матэматыка-кантэйнер"> $ е \ ль 3 v - 6 $ . См Wikipedia .

3
дададзена
робіць гэта змена наогул, калі асобы былі самі па сабе, пяцікутнік?
дададзена аўтар Sabha B, крыніца

This is only applicable to planar graphs, for instance $K_5$ has $5$ vertices but $10 > 15 - 6$ edges. This answer will give you a proof to this common theorem.

2
дададзена
робіць гэта змена наогул, калі асобы былі самі па сабе, пяцікутнік?
дададзена аўтар Sabha B, крыніца
Вы можаце фармаваць твар, як вы, але $ K_5 $ будуць непланарными незалежна ад таго, як вы малюеце яго.
дададзена аўтар Larry B., крыніца

This formula is valid specifically for planar graphs. If a graph with $3$ or more vertices is planar, and $e$ is the number of edges and $v$ the number of vertices of that graph, then it is true that $$ e \leq 3v-6 $$

1
дададзена
робіць гэта змена наогул, калі асобы былі самі па сабе, пяцікутнік?
дададзена аўтар Sabha B, крыніца
@DevAllanPer Вы не атрымаеце роўнасць, калі ёсць пяцівугольнікі (звярніце ўвагу, што кожнае Пяцівугольная асоба можа быць зроблена ў тры трохкутныя грані, дадаўшы два рэбры паміж вяршынямі). Так што можна было б умацаваць. Да таго, што? Я не ведаю. Нешта падобнае (я толькі мяркую, дзіка тут) $ е \ Leq V + 3 $, магчыма? Больш пільны погляд з формулай Эйлера, верагодна, выявіць фактычны адказ.
дададзена аўтар Ignacio Vazquez-Abrams, крыніца

Хай $ G $ быць плоскі граф, і хай $ F $ абазначаюць лік граняў і $ E $ пазначае лік рэбраў, а $ V $ пазначае лік вяршыняў. Формула Эйлера сцвярджае, што <�прамежак клас = "Math-кантэйнер"> $ V-E + F = 2 $ што азначае <�клас дыяпазон = "Math-кантэйнер"> $ F = 2 + EV $ , З іншага боку, даўжыня перыметра, навакольнага паверхню, па меншай меры <�пралёт клас = «Math-кантэйнер»> $ 3 $ . Такім чынам, калі падсумаваць даўжыню да кожнай асобы, якое ў два разы лік рэбраў, мы атрымліваем: <�Прамежак клас = "Math-кантэйнер"> $ 6 + 3E-3V = 3 (2 + EV) = Р * 3 \ Leq \ sum_ {е \ у асобе (G)} {LEN (е)} = 2 * Е $ . што азначае <�клас дыяпазон = "матэматыка-кантэйнер"> $ E \ Leq 3V-6 $ .

1
дададзена

That's the number of edges in a planar graph with all faces triangles, and thus the highest possible number of edges in a planar graph. \begin{align*}V+F &= E+2\\ V+\frac23 E &= E+2\\ V-2 &= \frac13E\\ 3V-6 &= E\end{align*}

0
дададзена
Так што гэта мяняе, калі асобы былі самі па сабе, пяцікутнік?
дададзена аўтар Sabha B, крыніца
Асобы з больш беражкамі прыводзяць да меншай колькасці агульных рэбраў. Вядома, мы заўсёды маглі б прыцягнуць новыя рэбры ў кожнай грані, скарачаючы іх да таго часу, толькі трыкутнікі застаюцца.
дададзена аўтар jmerry, крыніца