Grafs (simètrics o no dirigits)
-------------------------------


Conceptes
~~~~~~~~~

- `Graf (simètric o no dirigit)
  <https://ca.wikipedia.org/wiki/Graf_%28matem%C3%A0tiques%29#Graf_no_dirigit>`__

- `Vèrtex
  <https://ca.wikipedia.org/wiki/V%C3%A8rtex_(teoria_de_grafs)>`__

- `Aresta
  <https://ca.wikipedia.org/wiki/Aresta_(teoria_de_grafs)>`__

- `Veïnatge, adjacència o incidència
  <https://ca.wikipedia.org/wiki/Glossari_de_teoria_de_grafs#Ve%C3%AFnatge>`__

- `Grau <https://ca.wikipedia.org/wiki/Grau_(teoria_de_grafs)>`__

- `Camí
  <https://ca.wikipedia.org/wiki/Glossari_de_teoria_de_grafs#Camí>`__,
  `cicle
  <https://ca.wikipedia.org/wiki/Glossari_de_teoria_de_grafs#Cicle>`__

- `Connectivitat
  <https://en.wikipedia.org/wiki/Glossary_of_graph_theory_terms#connected>`__,
  `component
  <https://en.wikipedia.org/wiki/Glossary_of_graph_theory_terms#component>`__


NetworkX
~~~~~~~~

- La classe :class:`~networkx.Graph` implementa el concepte de graf
  simètric i ofereix mètodes per:

  - `afegir i esborrar vèrtexs i arestes
    <https://networkx.github.io/documentation/stable/reference/classes/graph.html#adding-and-removing-nodes-and-edges>`__,

  - `recórrer vèrtexs i arestes
    <https://networkx.github.io/documentation/stable/reference/classes/graph.html#reporting-nodes-edges-and-neighbors>`__
    (pertany vèrtex i aresta, conjunts de vèrtexs i arestes, veïns),

  - `comptar vèrtexs, arestes i veïns del graf
    <https://networkx.github.io/documentation/stable/reference/classes/graph.html#counting-nodes-edges-and-neighbors>`__
    (nombre de vèrtexs i d'arestes, grau),

  - `fer còpies del graf i calcular subgrafs
    <https://networkx.github.io/documentation/stable/reference/classes/graph.html#making-copies-and-subgraphs>`__.

- Només usarem algorismes de grafs simètrics pel càlcul de:

  - :py:mod:`Camins <networkx.algorithms.simple_paths>` i
    :py:mod:`camins mínims
    <networkx.algorithms.shortest_paths.generic>`.

  - :py:mod:`Components <networkx.algorithms.components>`.

  - Recorreguts en :py:mod:`profunditat
    <networkx.algorithms.traversal.depth_first_search>` i en
    :py:mod:`amplada
    <networkx.algorithms.traversal.breadth_first_search>`.


Exemples
~~~~~~~~

.. toctree::

   exemples-grafs-ops_basiques
   exemples-grafs-etiquetes
   exemples-grafs-camins
   exemples-grafs-components
   exemples-grafs-recorreguts


Exercicis
~~~~~~~~~

- Zones d'un joc de rol:

  - `Camí indirecte
    <https://www.cs.upc.edu/~tonis/inf/2014-2015-P-L4G40-enunciat.html#exercici-1-grafs-5-punts>`__
    (:download:`tests <2014-2015-P-L4G40/test1.txt>`,
    :download:`solució <2014-2015-P-L4G40/ex1.py>`).

  - `Zones unides per una carretera (etiquetes)
    <https://www.cs.upc.edu/~tonis/inf/2014-2015-P-L4G40-enunciat.html#exercici-2-grafs-5-punts>`_
    (:download:`tests <2014-2015-P-L4G40/test2.txt>`,
    :download:`solució <2014-2015-P-L4G40/ex2.py>`).

  - `Ruta alternativa
    <https://www.cs.upc.edu/~tonis/inf/2014-2015-P-examen-final-enunciat.html#exercici-4-grafs-2-punts>`_
    (:download:`tests <2014-2015-P-examen-final/test4.txt>`,
    :download:`solució <2014-2015-P-examen-final/ex4.py>`).

- `Nombres coprimers
  <http://www.cs.upc.edu/~tonis/inf/2014-2015-P-L4G30-enunciat.html>`_
  (:download:`coprimers.py <2014-2015-P-L4G30/coprimers.py>`; tests:
  :download:`test1.txt <2014-2015-P-L4G30/test1.txt>`,
  :download:`test2.txt <2014-2015-P-L4G30/test2.txt>`,
  :download:`test3.txt <2014-2015-P-L4G30/test3.txt>`; solucions:
  :download:`ex1.py <2014-2015-P-L4G30/ex1.py>`, :download:`ex2.py
  <2014-2015-P-L4G30/ex2.py>`, :download:`ex3.py
  <2014-2015-P-L4G30/ex3.py>`).

- :ref:`graf-d-un-laberint`.

- `Estacions de metro (etiquetes)
  <http://www.cs.upc.edu/~tonis/inf/2014-2015-T-L4G20-enunciat.html>`_
  (tests: :download:`test1.txt <2014-2015-T-L4G20/test1.txt>`,
  :download:`test2.txt <2014-2015-T-L4G20/test2.txt>`; solucions:
  :download:`ex1.py <2014-2015-T-L4G20/ex1.py>`, :download:`ex2.py
  <2014-2015-T-L4G20/ex2.py>`).

.. warning:: Assegureu-vos que el nom del fitxer sigui el que diu
             l'enunciat al descarregar-lo