559 \image html connected_components.png |
559 \image html connected_components.png |
560 \image latex connected_components.eps "Connected components" width=\textwidth |
560 \image latex connected_components.eps "Connected components" width=\textwidth |
561 */ |
561 */ |
562 |
562 |
563 /** |
563 /** |
|
564 @defgroup graph_isomorphism Graph Isomorphism |
|
565 @ingroup algs |
|
566 \brief Algorithms for testing (sub)graph isomorphism |
|
567 |
|
568 This group contains algorithms for finding isomorph copies of a |
|
569 given graph in another one, or simply check whether two graphs are isomorphic. |
|
570 |
|
571 The formal definition of subgraph isomorphism is as follows. |
|
572 |
|
573 We are given two graphs, \f$G_1=(V_1,E_1)\f$ and \f$G_2=(V_2,E_2)\f$. A |
|
574 function \f$f:V_1\longrightarrow V_2\f$ is called \e mapping or \e |
|
575 embedding if \f$f(u)\neq f(v)\f$ whenever \f$u\neq v\f$. |
|
576 |
|
577 The standard <em>Subgraph Isomorphism Problem (SIP)</em> looks for a |
|
578 mapping with the property that whenever \f$(u,v)\in E_1\f$, then |
|
579 \f$(f(u),f(v))\in E_2\f$. |
|
580 |
|
581 In case of <em>Induced Subgraph Isomorphism Problem (ISIP)</em> one |
|
582 also requires that if \f$(u,v)\not\in E_1\f$, then \f$(f(u),f(v))\not\in |
|
583 E_2\f$ |
|
584 |
|
585 In addition, the graph nodes may be \e labeled, i.e. we are given two |
|
586 node labelings \f$l_1:V_1\longrightarrow L\f$ and \f$l_2:V_2\longrightarrow |
|
587 L\f$ and we require that \f$l_1(u)=l_2(f(u))\f$ holds for all nodes \f$u \in |
|
588 G\f$. |
|
589 |
|
590 */ |
|
591 |
|
592 /** |
564 @defgroup planar Planar Embedding and Drawing |
593 @defgroup planar Planar Embedding and Drawing |
565 @ingroup algs |
594 @ingroup algs |
566 \brief Algorithms for planarity checking, embedding and drawing |
595 \brief Algorithms for planarity checking, embedding and drawing |
567 |
596 |
568 This group contains the algorithms for planarity checking, |
597 This group contains the algorithms for planarity checking, |