http://wiki.math.bme.hu/history/P%C3%A1ros_gr%C3%A1fok?feed=atom&Páros gráfok - Laptörténet2024-03-29T08:15:37ZAz oldal laptörténete a wikibenMediaWiki 1.18.1http://wiki.math.bme.hu/index.php?title=P%C3%A1ros_gr%C3%A1fok&diff=2577&oldid=prevKristofh, 2007. április 30., 20:57-n2007-04-30T20:57:31Z<p></p>
<table class='diff diff-contentalign-left'>
<col class='diff-marker' />
<col class='diff-content' />
<col class='diff-marker' />
<col class='diff-content' />
<tr valign='top'>
<td colspan='2' style="background-color: white; color:black;">←Régebbi változat</td>
<td colspan='2' style="background-color: white; color:black;">A lap 2007. április 30., 20:57-kori változata</td>
</tr><tr><td colspan="2" class="diff-lineno">1. sor:</td>
<td colspan="2" class="diff-lineno">1. sor:</td></tr>
<tr><td class='diff-marker'>−</td><td style="background: #ffa; color:black; font-size: smaller;"><div>Akkor nevezunk egy <math>G</math> <del class="diffchange diffchange-inline">grafot parosnak</del>, ha <math>G</math> csucsainak <del class="diffchange diffchange-inline">halmazat </del>fel tudjuk ugy osztani egy <math>A</math> <del class="diffchange diffchange-inline">es </del><math>B</math> halmazra, hogy az osszes <math>G</math>-beli <del class="diffchange diffchange-inline">elre </del>teljesul hogy az egyik <del class="diffchange diffchange-inline">vegpontja </del><math>A</math>-ban van, a <del class="diffchange diffchange-inline">masik </del>pedig <math>B</math>-ben. Egy <math>G</math> <del class="diffchange diffchange-inline">paros grafot kovetkezokeppen </del>jelolunk: <math>G</math> <math>=</math> <math>(A,B)</math>.</div></td><td class='diff-marker'>+</td><td style="background: #cfc; color:black; font-size: smaller;"><div>Akkor nevezunk egy <math>G</math> <ins class="diffchange diffchange-inline">gráfot párosnak</ins>, ha <math>G</math> csucsainak <ins class="diffchange diffchange-inline">halmazát </ins>fel tudjuk ugy osztani egy <math>A</math> <ins class="diffchange diffchange-inline">és </ins><math>B</math> halmazra, hogy az osszes <math>G</math>-beli <ins class="diffchange diffchange-inline">élre </ins>teljesul hogy az egyik <ins class="diffchange diffchange-inline">végpontja </ins><math>A</math>-ban van, a <ins class="diffchange diffchange-inline">másik </ins>pedig <math>B</math>-ben. Egy <math>G</math> <ins class="diffchange diffchange-inline">páros gráfot kovetkezoképpen </ins>jelolunk: <math>G</math> <math>=</math> <math>(A,B)</math>.</div></td></tr>
<tr><td class='diff-marker'> </td><td style="background: #eee; color:black; font-size: smaller;"></td><td class='diff-marker'> </td><td style="background: #eee; color:black; font-size: smaller;"></td></tr>
<tr><td class='diff-marker'>−</td><td style="background: #ffa; color:black; font-size: smaller;"><div>Teljes <del class="diffchange diffchange-inline">paros grafnak </del>nevezunk egy olyan <del class="diffchange diffchange-inline">paros grafot </del>melyben minden <math>A</math>-beli pont ossze van kotve minden <math>B</math>-beli ponttal. <del class="diffchange diffchange-inline">Jeloles</del>: <math>K_{a,b}</math>, ahol <math>a</math> <math>=</math> <math>|A|</math> <del class="diffchange diffchange-inline">es </del><math>b</math> <math>=</math> <math>|B|</math>.</div></td><td class='diff-marker'>+</td><td style="background: #cfc; color:black; font-size: smaller;"><div>Teljes <ins class="diffchange diffchange-inline">páros gráfnak </ins>nevezunk egy olyan <ins class="diffchange diffchange-inline">páros gráfot </ins>melyben minden <math>A</math>-beli pont ossze van kotve minden <math>B</math>-beli ponttal. <ins class="diffchange diffchange-inline">Jelolés</ins>: <math>K_{a,b}</math>, ahol <math>a</math> <math>=</math> <math>|A|</math> <ins class="diffchange diffchange-inline">és </ins><math>b</math> <math>=</math> <math>|B|</math>.</div></td></tr>
<tr><td class='diff-marker'> </td><td style="background: #eee; color:black; font-size: smaller;"></td><td class='diff-marker'> </td><td style="background: #eee; color:black; font-size: smaller;"></td></tr>
<tr><td class='diff-marker'>−</td><td style="background: #ffa; color:black; font-size: smaller;"><div>== <del class="diffchange diffchange-inline">Tetel </del>==</div></td><td class='diff-marker'>+</td><td style="background: #cfc; color:black; font-size: smaller;"><div>== <ins class="diffchange diffchange-inline">Tétel </ins>==</div></td></tr>
<tr><td class='diff-marker'> </td><td style="background: #eee; color:black; font-size: smaller;"></td><td class='diff-marker'> </td><td style="background: #eee; color:black; font-size: smaller;"></td></tr>
<tr><td class='diff-marker'>−</td><td style="background: #ffa; color:black; font-size: smaller;"><div>Egy G <del class="diffchange diffchange-inline">graf </del>akkor <del class="diffchange diffchange-inline">es </del>csak akkor <del class="diffchange diffchange-inline">paros</del>, ha minden G-beli kor <del class="diffchange diffchange-inline">paros hosszusagu</del>.</div></td><td class='diff-marker'>+</td><td style="background: #cfc; color:black; font-size: smaller;"><div>Egy <ins class="diffchange diffchange-inline"><math></ins>G<ins class="diffchange diffchange-inline"></math> gráf </ins>akkor <ins class="diffchange diffchange-inline">és </ins>csak akkor <ins class="diffchange diffchange-inline">páros</ins>, ha minden <ins class="diffchange diffchange-inline"><math></ins>G<ins class="diffchange diffchange-inline"></math></ins>-beli kor <ins class="diffchange diffchange-inline">páros hosszuságu.</ins></div></td></tr>
<tr><td colspan="2"> </td><td class='diff-marker'>+</td><td style="background: #cfc; color:black; font-size: smaller;"><div> </div></td></tr>
<tr><td colspan="2"> </td><td class='diff-marker'>+</td><td style="background: #cfc; color:black; font-size: smaller;"><div><ins class="diffchange diffchange-inline">====Bizonyitas:====</ins></div></td></tr>
<tr><td colspan="2"> </td><td class='diff-marker'>+</td><td style="background: #cfc; color:black; font-size: smaller;"><div> </div></td></tr>
<tr><td colspan="2"> </td><td class='diff-marker'>+</td><td style="background: #cfc; color:black; font-size: smaller;"><div><ins class="diffchange diffchange-inline">Az elso irány nyilvánvalo, ugyanis ha <math>C</math> egy kor a <math>G</math> páros gráfban, akkor <math>C</math> pontjai alternálnak <math>A</math> és <math>B</math> kozott. Tehát világos hogy <math>C</math>-nek páros sok csucsa van.</ins></div></td></tr>
<tr><td colspan="2"> </td><td class='diff-marker'>+</td><td style="background: #cfc; color:black; font-size: smaller;"><div> </div></td></tr>
<tr><td colspan="2"> </td><td class='diff-marker'>+</td><td style="background: #cfc; color:black; font-size: smaller;"><div><ins class="diffchange diffchange-inline">A másik irányhoz megmutatjuk, hogy ha <math>G</math> minden kore páros sok pontbol áll, akkor meg tudunk adni megfelelo <math>A</math> és <math>B</math> halmazokat. Tekintsunk egy tetszoleges <math>x</math> pontot a gráfban. Ezt rakjuk <math>A</math>-ba. Most, <math>x</math> minden szomszédját rakjuk <math>B</math>-be, és az osszes olyan <math>B</math>-beli pont szomszédját amelyet még nem helyeztunk el, rakjuk <math>A</math>-ba. Ezt folytassuk amig minden pontot el nem helyeztunk <math>A</math>-ba vagy <math>B</math>-be. Ez az algoritmus azért lesz jo, mert ha egy halmazban lenne két szomszédos csucs, akkor a gráfban lenne páratlan kor is, ez viszont ellentmondas</ins>.</div></td></tr>
</table>Kristofhhttp://wiki.math.bme.hu/index.php?title=P%C3%A1ros_gr%C3%A1fok&diff=2575&oldid=prevKristofh, 2007. április 30., 20:25-n2007-04-30T20:25:19Z<p></p>
<p><b>Új lap</b></p><div>Akkor nevezunk egy <math>G</math> grafot parosnak, ha <math>G</math> csucsainak halmazat fel tudjuk ugy osztani egy <math>A</math> es <math>B</math> halmazra, hogy az osszes <math>G</math>-beli elre teljesul hogy az egyik vegpontja <math>A</math>-ban van, a masik pedig <math>B</math>-ben. Egy <math>G</math> paros grafot kovetkezokeppen jelolunk: <math>G</math> <math>=</math> <math>(A,B)</math>.<br />
<br />
Teljes paros grafnak nevezunk egy olyan paros grafot melyben minden <math>A</math>-beli pont ossze van kotve minden <math>B</math>-beli ponttal. Jeloles: <math>K_{a,b}</math>, ahol <math>a</math> <math>=</math> <math>|A|</math> es <math>b</math> <math>=</math> <math>|B|</math>.<br />
<br />
== Tetel ==<br />
<br />
Egy G graf akkor es csak akkor paros, ha minden G-beli kor paros hosszusagu.</div>Kristofh