[index Math] Pour discuter de mathématique...

[Benoit]

Vu le nombre de prépas littéraires en France, ça ne serait probablement pas si compliqué de consacrer ces heures de Français à des cours "niveau khâgne" de différentes matières, au moins "pour voir", c'est pas comme si la matière avait une quelconque importance dans les concours.

[Ixy]

4) Existe-t-il un graphe dont tous les sommets ont un degré sortant strict. positif et qui n'admet pas de cycle ? Un cycle est un chemin dont le point de départ est aussi le pont d'arrivée. Quelle condition nécessaire doit vérifier un tel graphe ?

C'mon

[freeshost]

Des sommets extérieurs au graphe qui viennent nourrir celui-ci ?

[Ixy]

Non il n'y a pas de sommet extérieur mais...


Think outside the box

[freeshost]

Bon alors... un tel graphe comprend au moins un cycle au solde négatif ?

[Ixy]

Non

Autre formulation :
Montrer que pour un graphe à n sommets, il existe au moins un cycle si tous les sommets ont un degré sortant.

[freeshost]

Attends ! C'est quoi déjà, un degré sortant ?

Dans un cycle, chaque nœud a exactement une sortie et une entrée ?

J'apprends sur le tas. Je n'ai pas lu de livres ou de pdf sur le chapitre.

[Ixy]

C'est pour un graphe orienté, c'est le nombre de flèches partant de ce sommet. Un cycle est un chemin qui revient sur lui même, donc les neouds d un cycle ont un degré sprtant et entrant strict. positifs.

[freeshost]

2) Si pour un graphe il existe un chemin passant par toutes les arêtes, que peut-on dire sur le degré de chaque sommet ? Le degré d'un sommet est le nombre d'arêtes qui est relié à ce sommet.

Le degré de chaque sommet un multiple de 2 positif (strictement positif s'il y a un nombre strictement positif de nœuds). Le nombre de nœuds est un multiple de 2.

4) Existe-t-il un graphe dont tous les sommets ont un degré sortant strict. positif et qui n'admet pas de cycle ? Un cycle est un chemin dont le point de départ est aussi le pont d'arrivée. Quelle condition nécessaire doit vérifier un tel graphe ?

Un cycle est un chemin qui revient sur lui même, donc les neouds d un cycle ont un degré sprtant et entrant strict. positifs.

Je ne comprends pas le "donc". [Et donc je ne comprends pas la question 4.]

Enfin, oui, maintenant que tu parles d'orientation, je comprends mieux. Je croyais que chaque flèche entrante avait une valeur -1 pour le nœud où elle entrait.

Un sommet qui a un degré sortant strictement positif est un sommet qui a strictement plus de flèches qui partent de lui que de flèches qui arrivent vers lui ?

Si oui, j'aurais tendance à, dans un premier temps, revenir sur ma réponse précédente : la somme des degrés est nulle. Ensuite, est-ce que ça prouve qu'il y a forcément au moins un cycle ? Ben, la somme des degrés d'un cycle est nulle. Donc ça ne me semble pas possible, puisque la somme de nombres entiers strictement positifs ne peut être le nombre nul.

[Benoit]

Si tu définis un graphe à partir de (N, < ) <-> (v, E) tel que :
- chaque noeud correspond à un entier et un seul
- chaque lien est dans la direction correspondant à '<'

Tu as bien un graphe dont tous les noeuds ont un lien sortant (donc un outdegree non nul), et évidemment pas de cycle.

Par contre, est-ce que ce truc est un graphe étant donné que ses noeuds ne peuvent être comptés ?

[Ixy]

Bien joué Benoit. Bien sûr que N peut être compté ! N est dénombrable, c'est trivial si on revient à la définition. Mais ceci dit on a même pas besoin d'avoir un ensemble de noeuds dénombrables, ce pourrait être les nombres réels.

Freeshost : non le degré sortant on tient seulement compte des flèches sortantes.


Donc la condition nécessaire est que le graphe est infini !

[Benoit]

Ca rejoint ce que je disais, ça sert pas à grand chose un graphe infini dans l'informatique.

[Ixy]

On est sur le topic des mathématiques

[Bubu]

Rien de pire que :
- des mathématiciens qui se prennent pour des développeurs parce qu'ils ont écrit quelques dizaines de lignes dans tel script. (JavaScript, ou Python notamment).
- des informaticiens qui se prennent pour des mathématiciens parce qu'ils ont utilisé telle ou telle formule mathématique sans la comprendre.

Mais il existe des mathématiciens/informaticiens, compétents dans les deux domaines.

[Ixy]

Je suis entre les deux (data scientist).

J'adore cette citation :

Data Scientist (n.): Person who is better at statistics than any software engineer and better at software engineering than any statistician.