gerichteter Graph

[Han]

Hallo....ich hab da eine allgemeine Frage zu Graphen:

Wann ist in einem gerichteten Graphen ein Knoten zu einem anderen Knoten adjazent?

Angenommen mein Graph besteht aus 2 Knoten:A,B

Der Pfeil in der gerichteten Kante,die A und B miteinander verbindet, zeigt von A nach B.

Ist dann B ein benachbarter Knoten?

Und wie schauts aus wenn der Pfeil von B nach A zeigt?

mfg,
Hannes

 

[bygones]

in einer adjazenzmatrix ist eine 1 wenn eine Kante vorhanden ist, eine 0 wenn nicht.

D.h. wenn du eine gerichtete Kante von a -> b hast, so steht bei dem eintrag a/b eine 1, bei b/a eine 0.
geht die Kante von b->a so steht bei a/b 0 und bei b/a 1....

 

[Bleiglanz]

also bei A->B

01
00

und bei B->A

00
10

 

[Han]

Hallo....danke für die Antworten....habs jetzt einmal so implementiert wies ihr gesagt habt.

Ich hab dann aber noch eine Frage....

Und zwar hab ich eine Tiefensuche auch noch implementiert....welche bei der Methode isConnected(Graph g) zum Zug
kommt.

Angenommen ich habe einen Graph A->B->C<-D

Ist dann der Graph verbunden oder nicht? Denn bei der Tiefensuche würde es mir ja dann D nicht besuchen und ich habe isConnected so implementiert:

//Returns true if the graph is connected, false otherwise.
  public boolean isConnected() {
	  	
	  if(sizeVertices == 0){
		  return false;
	  }
	 
	  int[] val = dfs(0); //Tiefensuche welches Array zurückliefert mit besuchten Knoten.
	  
	  for(int i=0; i<val.length;i++){
		  if(val[i]==0){
			  return false;
		  }
	  }
	  return true;
  }

Also bei mir leifert dann isConnected() false.....was aber anschaulich irgendwie komisch erscheint...da ja der Graph verbunden ist...kann mir wer helfen?

mfg,
Hannes

 

[bygones]

nein er ist nicht verbunden, es fehlt ja eine Kante von C->D somit findest du beim startpunkt a bei tiefen-/breitensuche den Knoten D nicht !

 

[Han]

aha...passt dann hab ichs eh richtig....

mfg,
Hannes

 

[Han]

Hallo....jetzt hab ich noch eine Frage:

Wann ist in einem gerichteten Graphen eine Kante inzident?

Im Skript steht folgende Defnition:
Kante,die 2 adjazente Knoten verbindet,heißt inzident zu diesem Knoten.

Angenommen ich habe folgende Verbindung:
A->B

Ist dann die Kante inzident?...ich kapiers noch nciht ganz....

mfg,
Hannes

 

[byte]

Kante,die 2 adjazente Knoten verbindet,heißt inzident zu diesem Knoten.

Demnach ist die Kante inzident zum Knoten A und zum Knoten B.

 

[Han]

Na ja ich glaub so einfach is nicht...denn was is wenn ich wissen will ob die Kante bei Knoten B indizent ist.
Dann ist aber A kein adjazenter Knoten zu B. Also müsste demnach die Kante wenn man das Ganze von B aus betrachtet nicht indizent sein oder?
Umgekehrt aber schon oder?

mfg,
Hannes

 

[bygones]

indizenz kommt nur in einem ungerichteten Graphen vor !

Inzidenz bezeichnet eine Beziehung zwischen Knoten und Kanten in einem ungerichteten Graph. Ein Knoten heißt in einem ungerichteten Graph inzident mit einer Kante, wenn er von dieser Kante berührt wird, dass heißt, wenn diese ihn enthält.