generare Cicluri Hamiltoniene; graful este memorat prin matricea de adiacenta

Hamilton.java

/*
Grafuri
-------

Graf <=> orice multime finita V, prevazuta cu o relatie binara interna E

G = (V,E)

V = numarul de noduri
E = numarul de muchii

relatia binara

V = {1,2,3,4,5}

R: {1,2,3,4,5} -> {1,2,3,4,5}

E = ({1,2} {2,3} {4,5})

relatia binara este simetrica adica (1,2) (2,1) 

Graful este o reprezentare abstracta a conectivitatii folosind noduri si muchii

Graful poate sa fie orientat
                    neorientat


Graful neorientat <=> G = (V,E) relatia binara este simetrica

Graful orientat <=> G = (V,E) relatia binara nu ste simetrica


Node = element al multimii V, G = (V,E) graf neorientat sau orientat

Varf

muchie = element al multimii E ce descrie o relatie existenta intre doua varfuri  din V, unde G este graf neorientat

Arc = element al multimii E ce descrie o relatie existenta inrte doua varfuri din V unde G este graf orientat

Adiacenta = Varful w este adiacent cu v daca perechea (v,w) apartine lui E. 
intr-un graf neorientat existenta muchiei (v,w) presupune ca w este adiancent cu v si v este adiacent cu w


Incidenta <=> o muchie este incidenta cu un nod daca il are pe acesta extremitate.

Muchia (v,w)  este incidenta cu nodul v, respectiv cu nodul w;

Grad <=> gradul unui nod v , intr-un graf neorientat este un numar natural ce reprezinta numarul de noduri adiacente cu acesta

Grad interior <=> in cazul unui graf orientat, fiecare nod V are asociat un numar numit grad interior si care este egal cu numarul de arce care il au pe v ca varf terminal - numarul de arce incidente spre exterior

Gradul exterior <=> in cazul unui graf orientat. , fiecare nod v are asociat un n umar numit grad exterior si care este egal cu  numarul de arce care il au pe v ca varf initial (numarul de arce incidente spre exterior)

Varf izolat = un varf care are gradul 0

Grad exterior

Ciclu = Un lant in care primul nod coincide cu ultimul, Ciclul este elementar daca este format doar din noduri distincte, exceptie facand primul si ultimul
           
         6  
          \
  1      / 5       2,3,5,6 - lant elementar
  |    /   /
  2---3----4     5,3,4,5,6 - lant simplu nu este elemetnar pentru ca se repeta niste noduri

  3,4,5,3 - ciclu



Circuit

Drum = o secventa de varfuri ale unui graf orientat G = (V,E) cu proprietatea ca oricare doua varfuri consecutive sunt adiacente.


Subgraf si graf partial
-----------------------


Un Graf G' = (V',E') reprezinta un graf partial al lui G = (V,E) 

daca E' inclus in E . cu alte cuvinte G' este graf partial al lui G daca este identic sau se obtine prin suprimarea  unor muchii (respectic arce).

Un subgraf G'= (V',E') al lui G = (V,E) se obtine prin suprimarea unor noduri impreuna cu muchii /arcele  incidente cu acestea

Graf conex = graf neorientat in care , pentru oricare pereche de noduri (x,y) exista un lant care 
le uneste, exista un drum de la x la y sau de la y la x.

Lant hamiltonian = este un lant elementar  care contine toate nodurile unui graf

Ciclu hamiltonian = un ciclu elementar care contine toate nodurile grafului

Euler

Lant eulerian = un lant simplu care contine toate muchiile unui graf
 
Ciclu eulerian = un ciclu simplu care contine toate muchiile unui graf


1 2 3 4 5

Matricea de adiacenta

0 1 0 1 1
1 0 1 0 0
0 1 0 0 1
1 0 0 0 1
0 0 1 1 0
*/

import java.util.Scanner;

public class HamiltonianCycle {
	
	    static final int N = 50;

       static int n;

       static int path[] = new int[N];

       static int[][] matrix = new int[N][N];
       
       static boolean[] used = new boolean[N];

       static int startNode;


       public static void printSolution() {

       	  StringBuilder sb = new StringBuilder();

          for(int i = 1; i <= n; ++i) {

             sb.append(path[i]).append(" ");            
          }

          sb.append(startNode);

          System.out.println(sb);
       }

       public static void hamilton(int k) {

           if(k == n + 1) {

              if(matrix[startNode][path[k-1]] == 1) {

              	 printSolution();
              }

           } else {

              for(int v = 1; v <= n; v++) {

                  if(!used[v] && matrix[path[k-1]][v] == 1) {

                       path[k] = v;
                       used[v] = true;
                       hamilton(k+1);
                       used[v] = false;
                  }
              } 
           }              
       }

       public static void main(String[] args) {
              
        Scanner scanner = new Scanner(System.in);

              n = scanner.nextInt(); //citesc numarul de noduri

              startNode = scanner.nextInt(); //citesc nodul de start

              path[ 1 ] = startNode;                

              for(int i = 1; i <= n; ++i) used[i] = false;

              used[ startNode ] = true;


              for(int i = 1; i <= n; ++i) {
               
               for(int j = 1; j <= n; ++j) {

                  matrix[i][j] = scanner.nextInt();
              }  
             }

              hamilton( 2 );      
       }

}