Prüfer-kód

A Wikipédiából, a szabad enciklopédiából
Ugrás a navigációhoz Ugrás a kereséshez
Számozott fa, melynek Prüfer kódja: 4445.

A gráfelméletben egy n csúcsú számozott fa Prüfer-kódja egy n–2 hosszú számsorozat, melyet a későbbiekben részletezett szabály szerint rendelünk a fához. (A kód tulajdonképpen n–1 hosszúságú, csak az utolsó elem elhagyható, mert az mindig n.)

Prüfer-kód hozzárendelése számozott fához[szerkesztés]

Tekintsünk egy tetszőleges fát az {1,2…n} csúcsokon, és rendeljünk hozzá egy számsorozatot a következőképpen: Hagyjuk el a fa elsőfokú csúcsai közül azt, amelyiknek a legkisebb a sorszáma, és közben annak a csúcsnak írjuk fel a sorszámát, amellyel az elhagyott csúcs össze volt kötve. Legyen ez v1. Ezt ismételjük, amíg már csak egy csúcs marad. Nyilvánvaló, hogy ez a csúcs az n-edik sorszámú, hiszen egy fának mindig van legalább 2 elsőfokú csúcsa, és n-nél csak kisebb sorszámú csúcsok vannak, így előbb azokat hagyjuk el. Ezért a számsorozat végén nem is kell szerepelnie, hiszen egyértelmű. Az így kapott v1,v2,…,vn-2 számsorozat a fa Prüfer-kódja.

Algoritmus: Számozott fából Prüfer-kód[szerkesztés]

  • Bemenet egy számozott fa (csúcsait az 1, 2, ..., n számokkal címkézzük meg)
  • Végezzük el az alábbiakat mindaddig, amíg egyetlen él marad
  • válasszuk ki a legkisebb számú levelet (fokszáma 1),
  • írjuk ki a vele szomszédos csúcs számát,
  • töröljük a fából a kiválasztott csúcsot (természetesen a hozzáilleszkedő éllel együtt).
  • Az eredményül kapott számok a kiírás sorrendjében képezik a Prüfer-kódot.

A mellékelt ábrán
a legkisebb értékű levél az 1, tehát kiírjuk a 4-et, törüljük az 1-et
most legkisebb értékű levél a 2, kiírjuk a 4-et, töröljük a 2-t,
most legkisebb értékű levél a 3, kiírjuk a 4-et, töröljük a 3-t,
most legkisebb értékű levél a 4, kiírjuk az 5-öt, töröljük a 4-t,
egy él maradt, az (5,6), tehát vége. Eredmény: 4, 4, 4, 5.

Még egy példa:

Prufer-kode algoritmen.png
Számozott fából Prüfer-kód C++-ban
/* graf0.be tartalma pl. az ábra szerint:
6
1 4
2 4
3 4
4 5
5 6
*/

// Számozott fából Prüfer-kód

#include <iostream>
#include <fstream>

int n, m, a[50], b[50], fok[50];

// Bemeneti állomány: csúcsok száma, majd élek végpontjai (szóközzel elválasztva)
std::ifstream f("graf0.be");

// Adatok beolvasása
void olvas()
{
	int i;
	f >> n;
	m = n - 1;

	// Fokszámok nullázása
	for (i = 1; i <= n; i++)
		fok[i] = 0;

	// Élek beolvasása, fokszámok kiszámítása
	for(i = 1; i <= m; i++)
	{
		f >> a[i];
		f >> b[i];
		fok[ a[i] ]++;
		fok[ b[i] ]++;
	}
}
 
void pruefer()
{
	int i,j,k;
	for (i = 1; i <= n-2; i++)
	{
		j = 1;
		// Legkisebb számú levél keresése
		while ( (j<=n) && (fok[j]!=1) )
			j++;
		k = 1;
		while ( (k<=m) && (a[k]!=j) && (b[k]!=j )  )
			k++;
		// Kód újabb elemének kiírása
		if (a[k] == j)
			std::cout << b[k] << " ";
		else
			std::cout << a[k] << " ";
		fok[ a[k] ]--;
		fok[ b[k] ]--;
		a[k]=0;
		b[k]=0;
	}
}
 
int main()
{ 
	olvas();
	std::cout << std::endl;
	pruefer();
	std::cout << std::endl;
	return 0;
}

Számozott fa hozzárendelése Prüfer-kódhoz[szerkesztés]

Az első módszer alapötlete a következő: Hozzáadjuk a Prüfer-kódhoz utolsó elemként az n-et. Kiválasztjuk azt a legkisebb pozitív természetes számot, amelyik nem szerepel a sorozatban (Prüfer-kód, és n). A létrehozandó fában összekötjük ezt a számot a sorozat első elemével. Ezt a legkisebb számot hozzáadjuk a sorozathoz, majd töröljük a sorozat első elemét. Ezt a folyamatot addig folytatjuk, ameddig el nem fogynak az eredeti sorozat elemei.

Algoritmus: Prüfer-kódból számozott fa (1. módszer)[szerkesztés]

  • Bemenet: egy n-2 elemű Prüfer-kód, amelyhez hozzáadjuk az n értéket utolsónak.
  • Végezzük el n-1-szer a következőket:
  • meghatározzuk azt a legkisebb pozitív természetes számot, amelyik nem eleme a sorozatnak,
  • kössük össze egy éllel az ezzel a számmal jelölt csúcsot a sorozat első elemével,
  • töröljük a sorozat első elmét
  • Eredmény: a kapott fa

A mellékelt példa esetében a Prüfer-kód: 4,4,4,5. Az algoritmus lépései:

4 4 4 5 6 (1,4) él
4 4 5 6 1 (2,4) él
4 5 6 1 2 (3,4) él
5 6 1 2 3 (4,5) él
6 1 2 3 4 (5,6) él
Prüfer-kódból számozott fa (1. módszer) C++-ban
/* graf.be tartalma pl. az ábra szerint:
4
4 4 4 5
*/

// Prüfer-kódból számozott fa

#include <iostream>
#include <fstream>

int n, m, a[50];

// Bemeneti állomány: kód hossza, majd a kód elemei (szóközzel elválasztva)
std::ifstream f("graf.be");

// Adatok beolvasása
void olvas()
{
	int i;
	f >> n;
	for(i = 1; i <= n; i++)
		f >> a[i];
	n++;
	// Az utolsó elem hozzáadása
	a[n] = n+1;
}
 
// A sorozat ellenőrzése
void ellenoriz()
{
	int i;
	for (i = 1; i <= n; i++)
		if (a[i]>n+1)
		{
			std::cout << "A sorozat nem lehet fa ";
			exit(1);
		};
}

void pruefer()
{
	int i, j, min;
	m = n;
	for(i = 1; i <= n; i++)
	{
		min = 0;
		do
		{
			// A legkisebbb szám, amely nincs benne az a[i], ..., a[m] sorozatban
			min++;
			j = i;
			while ((j<=m) && (a[j]!=min))
				j++;
		} while (j <= m);
		m++;
		// A legkisebb elem hozzáadása a sorozathoz
		a[m] = min;
		// Él kiírása
		std::cout << "(" << min << "," << a[i] << ")" << std::endl;
	} 
}

int main()
{
	olvas();
	std::cout << std::endl;
	ellenoriz();
	pruefer();
	return 0;
}

A második módszer alapötlete a következő: A Prüfer-kódból kiszámítjuk az egyes csúcsok fokszámát, majd ezek alapján berajzoljuk a fa éleit, mindig levelet (1 fokszámú csúcsot) keresve.

Algoritmus: Prüfer-kódból számozott fa (2. módszer)[szerkesztés]

  • Bemenet: Prüfer-kód
  • Kiszámítjuk a csúcsok fokszámát a következőképpen:
  • kezdetben minden fokszám 1, az i csúcs fokszámát jelölje fi,
  • a Prüfer-kód minden i elemére, növeljük 1-gyel az fi-t,
  • a Prüfer-kód minden i elemére végezzük el:
  • keressük meg az f sorozat első 1-es elemét, legyen ennek a sorszáma j,
  • kössük össze egy éllel az i és j csúcsokat,
  • csökkentsük 1-gyel az fi és fj értékeket.
  • f-ben két 1-gyel egyenlő elem marad, legyenek ezek fi és fj; kössük össze az i csúcsot a j csúccsal.
  • Eredmény: az élekből összeálló fa.

A mellékelt ábra esetében a Prüfer-kód 4,4,4,5, az algoritmus lépései:

A fokszámsorozat: 1,1,1,4,2,1.

Kód: 4,4,4,5
Fokszámsorozat: 1,1,1,4,2,1 él: (1,4)

Kódrész: 4,4,5
Fokszámsorozat: 0,1,1,3,2,1 él: (2,4)

Kódrész: 4,5
Fokszámsorozat: 0,0,1,2,2,1 él: (3,4)

Kódrész: 5
Fokszámsorozat: 0,0,0,1,2,1 él: (4,5)

Kódrész:
Fokszámsorozat: 0,0,0,0,1,1 él: (5,6)

Prüfer-kódból számozott fa (2. módszer) C++-ban
/* graf.be tartalma pl. az ábra szerint:
4
4 4 4 5
*/

// Prüfer-kódból számozott fa

#include <iostream>
#include <fstream>

int n, a[50], fok[52];

// Bemeneti állomány: kód hossza, majd a kód elemei (szóközzel elválasztva)
std::ifstream f("graf.be");

// Adatok beolvasása
void olvas()
{
	int i;
	f >> n;
	for (i = 1; i <= n; i++)
		f >> a[i];
}

// A sorozat ellenőrzése
void ellenoriz()
{
	int i;
	for (i = 1; i <= n; i++)
		if (a[i] > n+1)
		{
			std::cout << "a sorozat nem lehet fa ";
			exit(1);
		};
}

// Az egyes csúcsok fokszámának kiszámítása
void fokszam()
{
	int i;
	for (i = 1; i <= n+2; i++)
		fok[i] = 1;
	for (i = 1; i <= n; i++)
		fok[ a[i] ]++;
}

void pruefer()
{
	int i, j, k;
	for (i = 1; i <= n; i++)
		for (j=1; j<=n+2; j++)
		{
			if (fok[j]==1)
			{
				std::cout << "(" << j  << "," << a[i] << ")" << std::endl;  // él kiírása
				fok[ a[i] ]--;
				fok[j]--;
				break;
			}
		}
	k = 1;
	while ( (k<=n+2) && (fok[k]!=1) )
		k++;
	std::cout << "(" <<  k << ",";             // utolsó él egyik csúcsa
	k++;
	while ( (k<=n+2) && (fok[k]!=1) )
		k++;
	std::cout <<  k << ")";                // utolsó él másik csúcsa
}

int main()
{
	olvas();
	std::cout << std::endl;
	ellenoriz();
	fokszam();
	pruefer();
	std::cout << std::endl;
	return 0;
}

Története[szerkesztés]

Heinz Prüfer 1930-ban

A Prüfer-kódot először Heinz Prüfer alkalmazta 1918-ban, melynek segítségével bizonyította a Cayley-formulát.

Források[szerkesztés]

  • Prüfer, H. (1918). „Neuer Beweis eines Satzes über Permutationen”. Arch. Math. Phys. 27, 742–744. o.  
  • Katona Gyula Y., Recski András, Szabó Csaba: Gráfelmélet, algoritmuselmélet és algebra, Typotex Kiadó, 2002.

További információk[szerkesztés]